欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 文旅 > 手游 > 单链表算法题(数据结构)

单链表算法题(数据结构)

2025/9/15 10:16:54 来源:https://blog.csdn.net/OKkankan/article/details/143608430  浏览:    关键词:单链表算法题(数据结构)

1. 反转链表

https://leetcode.cn/problems/reverse-linked-list/description/

题目

看到这个题目的时候我们怎么去想呢?如果我们反应快的话,应该可以想到我们可以从1遍历到5然后依次头插,但是其实我们还有更好的办法,就是利用三个指针,如何使用呢?

反转链表OJ
假如结构体已经给出
typedef struct ListNode SL;
SL* reverseList(SL* head)
{//处理空链表if (head == NULL){return head;}else{//创建三个指针SL* n1, n2, n3;n1 = NULL, n2 = head, n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3){n3 = n3->next;}}return n1;}
}

 2. 链表的中间结点

https://leetcode.cn/problems/middle-of-the-linked-list/description/
题目
 这个题目就是在一个链表中我们要返回中间结点,如果中间结点有两个的话就返回第二个结点。

对于这个题目我们可能会想到一个简单的思路,就是遍历两边数组然后找到中间的一个结点,但是呢,今天讲一个更方便的算法叫做快慢指针,也就如上图所示,一个慢指针和一个快指针,快指针走两步慢指针走一步,最终当快指针走到终的时候慢指针刚好就在中间,让我们来实现一下:

//找链表的中间结点
//Definition for singly-linked list.
struct ListNode
{int val;struct ListNode *next;
};typedef struct ListNode SL;
struct ListNode* middleNode(struct ListNode* head)
{SL* slow = head;SL* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

再上一个题目中我们有一个点需要注意就是我们在写while循环的条件时候注意不能将fast&&fast->next的位置搞反,原因就是不能解引用空指针,所以顺序一定注意一下。

3.  合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/description/

题目:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。这个题目的思路也很好想出来,我们可以遍历两个升序链表,然后创建一个新的链表,将遍历的结点按升序放入新的链表中,要注意链表为空的情况。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode SL;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{//创建新的链表SL* newhead=NULL;SL* newtail=NULL;//创建两个指针分别指向两个链表SL* l1=list1;SL* l2=list2;//判断两个链表是否为空if(list1==NULL){return l2;}if(list2==NULL){return l1;}while(l1&&l2){if(l1->val<=l2->val){//l1尾插到新链表中if(newhead==NULL){newhead=newtail=l1;}else{newtail->next=l1;newtail=newtail->next;}l1=l1->next;}else{//l2尾插到新链表中if(newhead==NULL){newhead=newtail=l2;}else{newtail->next=l2;newtail=newtail->next;}l2=l2->next;}}//跳出循环有两种情况,要么l1为空,要么l2为空if(l1){newtail->next=l1;}if(l2){newtail->next=l2;}return newhead;
}

4. 链表的回文结构

https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa

什么是回文结构?比如1221,它看起来像是对称的可以从中间重叠的感觉,叫做回文数字。像上图1->2->2->1,就是链表的回文结构。我们就是思考如何去判读一个链表是否是回文结构。我们可能会想到说这个题目需要去遍历比较是否相等,但是有一个问题就是在单链表中是不能向后遍历的,又因为这个题目是的链表长度是有限的,所以我们不妨把链表放入数组中来比较,那么如何操作呢?

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code here//创建一个数组int arr[900] = {0};ListNode* pcur = A;int i = 0;//遍历链表,将链表中的每个结点的数值放入数组中while(pcur){arr[i++] = pcur->val;pcur=pcur->next;}//找中间结点,判断是否是回文数字int left=0;int right=i-1;while(left<right){if(arr[left]!=arr[right]){return false;}left++;right--;}return true;}
};

对于这个题目来说,它是有限制的,所以我们可以放在数组中去双向遍历,但是一旦链表没有限制,我们就不能这样来写,我们可以有另一种方法,我们的前两道题目是反转链表和找中间结点,看下面的图,如果是回文链表的话我们可以先找到中间结点,然后将其反转成为一个新的链表,再创建两个指针遍历链表,判断链表结点是否相等,最终以一个指针为NULL而结束。

5. 相交链表

https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{//创建两个指针遍历链表ListNode* l1=headA;ListNode* l2=headB;//先计算两个链表的长度int sizeA=0;int sizeB=0;while(l1){sizeA++;l1=l1->next;}while(l2){sizeB++;l2=l2->next;}//得出了两个链表的长度//计算两数之差int gap=abs(sizeA-sizeB);//让长链表先走gap步ListNode* longlist=headA;ListNode* shortlist=headB;if(sizeA<sizeB){longlist=headB;shortlist=headA;}while(gap--){longlist=longlist->next;}//此时在同一个起点处,进行两个链表结点的比较while(longlist&&shortlist){if(longlist==shortlist){return longlist;}longlist=longlist->next;shortlist=shortlist->next;}//链表不相等return NULL;
}

 6. 环形链表

https://leetcode.cn/problems/linked-list-cycle/description/

题目:给你一个链表的头节点 head ,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ,则返回 true 。 否则,返回 false 。

💡 快慢指针
快慢指针,即慢指针一次走一步,快指针一次走两步,两个指针从链表起始位置开始运行,
如果链表带环则一定会在环中相遇,否则快指针率先走到链表的未尾。

对于这个题目我们可以使用快慢指针的方法进行解题,因为在环形链表中一个慢指针每次走一步一个快指针每次走两步一定还会相遇,如果相遇的话那么就证明这个链表是环形链表,为什么快慢指针一定会相遇呢?当slow和fast进入环之后,此时快慢指针在环里开始进行追逐,大家会发现它们之间的距离越来越凶小,从N变成N-1变成N-2....一直到0就是指针相遇。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode SL;
bool hasCycle(struct ListNode *head) 
{SL* slow=head;SL* fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){return true;}}//两个指针始终没有相遇return false;
}
思考2:快指针一次走3步,走4步,...n步行吗?
按照上面的分析,慢指针每次走一步,快指针每次走三步,此时快慢指针的最大距离为N,接下来的追逐过程中,每追击一次,他们之间的距离缩小2步,追击过程中fast和slow之间的距离变化:

 

分析:
1、如果N是偶数,第⼀轮就追上了
2、如果 N是奇数 ,第⼀轮追不上,快追上,错过了,距离变成-1,即C-1,进⼊新的⼀轮追击
a、C-1如果是偶数,那么下⼀轮就追上了
b、 C-1如果是奇数, 那么就永远都追不上
总结⼀下追不上的前提条件: N是奇数,C是偶数

 

假设:
环的周长为C,头结点到slow结点的长度为L,slow走⼀步,fast走三步,当slow指针入环后,
slow和fast指针在环中开始进行追逐,假设此时fast指针已经绕环x周。
在追逐过程中,快慢指针相遇时所走的路径长度:
fast: L+xC+C-N
slow L
由于慢指针走一步,快指针要走三步,因此得出: 3 * 慢指针路程 = 快指针路程 ,即:
3 L = L + xC + C N
2 L = ( x + 1) C N
对上述公式继续分析:由于偶数乘以任何数都为偶数,因此 2L一定为偶数,则可推导出可能得情
况:
情况1:偶数 = 偶数 - 偶数
情况2:偶数 = 奇数 - 奇数
由step1中(1)得出的结论,如果N是偶数,则第⼀圈快慢指针就相遇了。
由step1中(2)得出的结论,如果N是奇数,则fast指针和slow指针在第⼀轮的时候套圈了,开始进行下⼀轮的追逐;当N是奇数,要满足以上的公式,则 (x+1)C 必须也要为奇数,即C为奇数,满足a中的结论,则快慢指针会相遇。
因此, step1 中的 N 是奇数, C 是偶数 ,既然不存在该情况,则快指针⼀次⾛3步最终⼀定也
可以相遇。

 

 

 

 

 

 

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词