题目描述 用C++实现含头结点的单链表,然后实现单链表的两个结点交换位置。...注意不能简单交换两个结点包含数据,必须通过修改指针来实现两个结点的位置交换 交换函数定义可以参考: swap(int pa, int pb) //pa和pb表示两个结点在单链表的位置序号 swap...输出 第一行输出单链表创建后的所有数据,数据之间用空格隔开 第二行输出执行第1次交换操作后的单链表数据,数据之间用空格隔开 第三行输出执行第2次交换操作后的单链表数据,数据之间用空格隔开 如果发现输入位置不合法...int data; ListNode * next; ListNode() { data = -9999, next = NULL; } }; class LinkList { //带头结点的单链表...,位置从0到n,0是头结点,1是首结点,n是尾结点 private: ListNode * head; //头结点 int size; //表长 public: LinkList();
力扣链接 一般我们想到的会是 先遍历一次知道链表结点的个数后再除二,然后再遍历一次进行查找,但是这种做法需要遍历两次链表,消耗比较大,但是使用了快慢指针法就相对简单了,只需遍历一次....struct ListNode* slow,*fast;//定义快慢两个指针 slow = fast = head; while(fast && fast->next)//考虑到结点个数的奇偶
PS:链表是一种数据结构,而数据结构就是一种存放数据的方式。 为什么需要链表? 我们知道,数组也可以存储数据,那么为什么还需要链表呢?...接下来,我们来看看数组 和链表的区别: 1、数组就像身上编了号站成一排的人,要找第10个人很容易,根据人身上的编号很快就能找到。...链表示意图 链表的建立 class TestLink{//创建一个外部类 private Entry head;//指向头结点的引用 public TestLink(){ head =...new Entry();//用结点类 new 一个头结点 } class Entry{//Entry 创建一个结点内部类 int data;//定义数据块 Entry next;//...= null){ cur = cur.next; } Entry entry = new Entry(val);//得到的结点 cur.next = entry; } //得到单链表的长度
=x; s->next=L->next; L->next=s; //将新结点插入链表中 scanf("%d",&x); } return L;...j<i) //从第一个结点开始查找,查找第i个结点 { p=p->next; j++; } return p; //返回第i个结点的指针,若i大于表厂则返回...printf("被删除的值为:%d\n",x); int length=ListLength(mylist); printf("当前单链表的长度为:%d\n",length); while...NULL) { printf("查找成功"); } else { printf("查找失败"); } } return 0; } 运行结果: 注意:这是带头结点的单链表...,所以0号节点是头结点,查找0号结点是可以查找成功的。
题目描述 给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。 解题思路 一种方法是用 hashmap来存储和查找节点; 另一种方法是双指针法。...假设环长度为n,进入环之前结点个数为x,slow在环内走了k个结点,fast绕环走了m圈,则有2(x+k)=x+mn+k 可以得出x = mn - k。...此时slow距入口结点还剩 n-k个结点,x=(m−1)n+n−k,即一个指针从链表头节点走到环入口的长度等于另一个指针从相遇的位置走 m-1圈后再走n-k的长度,也就是说两个指针相遇后,让一个指针回到头节点...所以,我们设置两个指针,一个是快指针fast,一个是慢指针slow,fast一次走两步,slow一次走一步,如果单链表有环那么当两个指针相遇时一定在环内。...此时将一个指针指到链表头部,另一个不变,二者同时每次向前移一格,当两个指针再次相遇时即为环的入口节点。如果fast走到null则无环。
解题描述 方法1 - 哈希法,需要额外空间 1、遍历单链表的每个结点 2、如果当前结点地址没有出现在set中,则存入set中 3、否则,出现在set中,则当前结点就是环的入口结点 4、整个单链表遍历完...遍历整个链表的结点 空间复杂度O(N):其中 N 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。...1、初始化:快指针fast指向头结点, 慢指针slow指向头结点 2、让fast一次走两步, slow一次走一步,第一次相遇在C处,停止 3、然后让fast指向头结点,slow原地不动,让后fast...,slow每次走一步,当再次相遇,就是入口结点。...在最初判断快慢指针是否相遇时,slow 指针走过的距离不会超过链表的总长度;随后寻找入环点时,走过的距离也不会超过链表的总长度 空间复杂度O(1):额外使用的指针占用常数空间
头指针 指示链表中第一个结点(即第一个数据元素的存储映像)的存储位置。同时,由于最后一个数据元素没有直接后继,则线性链表中最后一个结点的指针为“空”(NULL)。 ?..., *LinkList; 有时在单链表的第一个结点之前附设一个结点,称之为头结点 。...若线性表为空,则头结点的指针域为“空”,如图2(b)所示。 ? 图2 带头结点的单链表 (a)非空表;(b)空表 循环链表 是另一种形式的链式存储结构。...它的特点是表中最后一个节点的指针域指向头结点,整个链表形成一个环。由此,从表中任一结点出发均可找到表中其他结点,如图3所示为单链的循环链表 。 ?...图5 双向链表示例 (a)结点结构;(b)空的双向循环链表;(c)非空的双向循环链表
题:编写程序实现单链表的插入。...= NULL) { std::coutdata "; p = p->next; } std::cout<<std::endl; } } //单链表删除结点...free(p1); } } else { std::cout<<num<<" could not been found"<<std::endl; } return head; } //插入结点...head; } int _tmain(int argc, _TCHAR* argv[]) { node *head; head = create(); print(head); //删除结点...int num; std::cin>>num; head = del(head, num); print(head); //打印删除后的单链表 //插入结点 std::cin>>num;
题目描述 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。...例如,链表1->2->3->3->4->4->5 处理后为 1->2->5 解题思路 首先添加一个头节点,以方便碰到第一个,第二个节点就相同的情况 设置 first ,second 指针, first
一、题目描述 给定一个头结点为 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。...示例 1: 输入:[1,2,3,4,5] 输出:此列表中的结点 3 (序列化形式:[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。...示例 2: 输入:[1,2,3,4,5,6] 输出:此列表中的结点 4 (序列化形式:[4,5,6]) 由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。...提示: 给定链表的结点数介于 1 和 100 之间。 二、题目解析 我个人认为这道题目是最好理解快慢指针这个知识点了。 废话不多说,直接先来看动画演示!...三、参考代码 // LeetCode 100 题精讲:https://mp.weixin.qq.com/s/yznC53g46phq3qF7V4-obA // 作者:程序员吴师兄 // 链表的中间结点(
题目描述 输入一个链表,输出该链表中倒数第k个结点。 解题思路 经典的双指针法。...定义两个指针,第一个指针从链表的头指针开始遍历向前走k-1步,第二个指针保持不动,从第k步开始,第二个指针也开始从链表的头指针开始遍历,由于两个指针的距离保持在k-1,当第一个指针到达链表的尾节点时,第二个指针刚好指向倒数第...链表头指针是否为空,若为空则直接返回回null 2. k是否为0,k为0也就是要查找倒数第0个节点,由于计数一般是从1开始的,所有输入0没有实际意义,返回null 3. k是否超出链表的长度,如果链表的节点个数少于...if(head == null || k == 0) return null; ListNode temp = head; //判断k是否超过链表节点的个数...pA = pA.next; pB = pB.next; } return pB; } } 当然,还有一种是用stack的方法,把链表按顺序压入
ListNode deleteDuplication(ListNode pHead) { if (pHead == null || pHead.next == null) { // 只有0个或1个结点...,则返回 return pHead; } if (pHead.val.equals(pHead.next.val)) { // 当前结点是重复结点...= null && pNode.val.equals(pHead.val)) { // 跳过值与当前结点相同的全部结点,找到第一个与当前结点不同的结点...pNode = pNode.next; } return deleteDuplication(pNode); // 从第一个与当前结点不同的结点开始递归...} else { // 当前结点不是重复结点 pHead.next = deleteDuplication(pHead.next); // 保留当前结点,从下一个结点开始递归
思路 一次遍历链表,寻找中间节点。两个信息,一、要遍历完,二、遍历完时需要遍历到中间节点。所以需要两个指针,并且速度是1:2。注意题目要求中点为两个时,取后面个。...题目 给定一个头结点为 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。...示例 1: 输入:[1,2,3,4,5] 输出:此列表中的结点 3 (序列化形式:[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。...示例 2: 输入:[1,2,3,4,5,6] 输出:此列表中的结点 4 (序列化形式:[4,5,6]) 由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。...提示: 给定链表的结点数介于 1 和 100 之间。
在c++的线性表中,如何用ListNode设置好结点呢?...我们往往因为不熟悉指针和内存分配的原理,而在初学阶段不能正确的设置好结点,我总结了俩种不同情况设置结点的情况,这里引用LeetCode的几个题目为例 一、设置一个结点指向头结点head 如:ListNode...* p = head; 在这里面我们设置了一个结点指向head,我们用它可以帮助我们遍历整个链表 在c++中如果我们需要求一个链表的长度时时候就可以这样设置 剑指 Offer 22....这一道题你在求解过程需要求链表长度 ,通过ListNode *pre = head;设置pre这个结点可以帮助遍历链表 class Solution { public: ListNode* getKthFromEnd...合并两个有序链表 题解 C++ [链表]leetcode725-分隔链表(C++) (如果本篇文章有错误的地方,请及时指正,感谢你的阅读)
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。...第一种解法: 利用set存储每个结点,如果出现过则返回该结点,如果遍历完了都没找到则返回null 第二种解法: 双指针法: 定义两个指针,一个一次走两步的快指针一个慢指针,如果有环存在,则他们一定会在环上某个结点相遇....这时候他们都开始每次都一步,则下次相遇的点一定是环入口结点....2、两个指针分别从链表头和相遇点继续出发,每次走一步,最后一定相遇与环入口。 思路2证明如下 证明结论1:设置快慢指针fast和low,fast每次走两步,low每次走一步。...,下一次相遇就是那个环结点.
题目描述 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,返回链表头指针。...情况一 去掉重复部分保留一个 例如,链表1->2->3->3->4->4->5 处-理后为 1->2->3->4->5 代码: public ListNode deleteDuplication(ListNode...=null){ if (curr.val==pre.val){//如果当前结点的值和前一结点重复 pre.next=curr.next;...pre和curr是工作指针,用来往后撸链表,留有用的. 看完代码的应该理解实际上我这里类似于用preNotParall来选取有用结点组成新链表....= null) { if (curr.val == pre.val) {//如果当前结点的值和前一结点重复 //继续往下找,直到当前结点和前一结点值不同
链表的中间结点 链接 链表的中间结点 给定一个带有头结点 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。...示例 1: 输入:[1,2,3,4,5] 输出:此列表中的结点 3 (序列化形式:[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。...示例2: 输入:[1,2,3,4,5,6] 输出:此列表中的结点 4 (序列化形式:[4,5,6]) 由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。...提示: 给定链表的结点数介于 1 和 100 之间。...解题思路 定义一个快指针fast 一个慢指针slow ,快指针一次移动两个结点,慢指针一次移动一个结点 当fast到达链表的尾部结点时,慢指针也就移动到了链表的中间结点(同化成一个路程问题,同一段路程,
反转链表 力扣题目链接[1] 给你单链表的头节点 head,请你反转链表,并返回反转后的链表。...最终pre的指向就是翻转前链表的尾部节点,也是翻转后链表的头部,返回pre即可。 链表 /** * Definition for singly-linked list....链表的中间结点 力扣题目链接[2] 给定一个头结点为 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。...示例 2: 输入:[1,2,3,4,5,6] 输出:此列表中的结点 4 (序列化形式:[4,5,6]) 由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。...包括寻找链表的中间节点、检查链表是否存在环。都需要重点掌握。复杂度方面,时间复杂度是链表长度的一半,也就是O(n),维护了两个常数级别的变量,因此空间复杂度是O(1)。
题目描述 给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。 思路1....环即两次出现的结点,所以我们可以利用set存储,如果存的时候发现某个结点已经存储了,则,这个结点就是环入口 代码: //题目描述 //给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null....这时候他们都开始每次都一步,则下次相遇的点一定是环入口结点....所以两个指针分别从链表头和相遇点出发,最后一定相遇于环入口。...,下一次相遇就是那个环结点.
链表的中间结点) https://leetcode-cn.com/problems/middle-of-the-linked-list/ 题目描述 给定一个头结点为 head 的非空单链表,返回链表的中间结点...如果有两个中间结点,则返回第二个中间结点。 示例 1: 输入:[1,2,3,4,5] 输出:此列表中的结点 3 (序列化形式:[3,4,5]) 返回的结点值为 3 。...(测评系统对该结点序列化表述是 [3,4,5])。...示例 2: 输入:[1,2,3,4,5,6] 输出:此列表中的结点 4 (序列化形式:[4,5,6]) 由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。 ...提示: 给定链表的结点数介于 1 和 100 之间。
领取专属 10元无门槛券
手把手带您无忧上云