设为首页收藏本站
开启辅助访问

【单链表经典习题讲解】

 您所在的位置：网站首页 › 数据的分析经典例题 › 【单链表经典习题讲解】

【单链表经典习题讲解】

2024-07-05 02:56| 来源: 网络整理| 查看: 265

 大家好呀，今天向大家分享的是关于单链表的一些比较基础且经典的题目，相信你看完了一定会对单链表的知识掌握的更加熟练。

目录

1 移除链表元素

2 反转链表

3 链表的中间结点

4 链表中倒数第k个结点

 5 合并两个有序链表

6 链表分割

7 链表的回文结构

8 相交链表

9 环形链表

10 环形链表

 

 

 

1 移除链表元素

题目描述：

3faf08e7c1774f8a9c6e5512fa5e5301.png

 解题思路：

遍历链表，用cur表示当前位置，记录要去除元素的前一位地址（prev），让prev->next=cur->next.然后不断迭代，直至cur为空.

但是要额外处理当第一个元素就是要去除元素这种情况。

具体代码实现：

struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* prev=NULL; struct ListNode* cur=head; while(cur) { if(cur->val == val) { //头删 if(cur == head) { head=cur->next; free(cur); cur=head; } else { prev->next=cur->next; free(cur); cur=prev->next; } } else { prev=cur; cur=cur->next; } } return head; }

结果展示：

75594522d02f49b48770b50f5b15a771.png

 

2 反转链表

题目描述：

009a4b42159f4c3ba17a56a050f5daf2.png

 解题思路1：

遍历链表，让cur指向当前位置，记录cur前一位的位置prev,记录cur后一位位置next,让cur->next=prev,将prev=cur,cur=next,next=next->next,然后不断迭代，结束条件是cur为NULL，但是要注意当next为NULL时就不要进行next=next->next。

 789e8cdd2f444458838541f3dafbc98f.png

 具体代码：

ListNode* reverseList(struct ListNode* head) { if(head==NULL) { return head; } struct ListNode* prev=NULL; struct ListNode* cur=head; struct ListNode* next=head->next; while(cur) { //翻转 cur->next=prev; prev=cur; cur=next; if(next) { next=next->next; } } return prev; }

结果展示：

7bf692c311404d3695f76f67e79398bb.png

 

解题思路2：

遍历链表，将链表中的元素头插到一个新链表的头上，然后迭代下去，直到cur为NULL，但是要注意保存cur的下一个位置。

具体代码：

struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur=head; struct ListNode* newhead=NULL; while(cur) { struct ListNode* next=cur->next; cur->next=newhead; newhead=cur; cur=next; } return newhead; }

结果展示：

f63813352cb54a0bafd45f25ff7791e9.png

 两种方法都是可行的，具体用哪一种可以自己选择，但是不要刻意去关注leetcode结果展示中的执行用时和内存消耗，这可能与网速有关。

3 链表的中间结点

题目描述：

435500df58ec496d9aae0184b785630f.png

 解题思路：

常规思路：遍历链表求链表长度，然后再遍历一遍数组求中间结点

具体代码：

struct ListNode* middleNode(struct ListNode* head) { int count=0; struct ListNode* cur=head; while(cur) { count++; cur=cur->next; } cur=head; int i=0; for(i=0;inext; } return cur; }

这种方法可行，但是有没有其他方法只遍历一遍链表呢？

快慢指针：让slow一次走一步，fast一次走两步，直到fast或者fast->next为NULL时结束，此时slow就是中间结点。

具体代码：

struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow=head; struct ListNode* fast=head; while(fast && fast->next) { slow=slow->next; fast=fast->next->next; } return slow; }

结果展示：

2b180bbac0164352ab497a2f1ed98441.png

  4 链表中倒数第k个结点

 

题目描述：

deabb4e1c2de483cbdb8ec770c630ac6.png

 解题思路：

仍然用快慢指针解题，让快指针先走k步，然后同时走。

具体代码：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode* slow=pListHead; struct ListNode* fast=pListHead; while(k--) { if(!fast) return NULL; fast=fast->next; } while(fast) { slow=slow->next; fast=fast->next; } return slow; }

其中值得注意的是当fast先走时并且当fast为空时直接返回NULL。

结果展示：

0b31656343f54542a55b20f909f88bd1.png

 5 合并两个有序链表

题目描述：

dd464e065c5e4bc7ac256c8f1188fd9a.png

 解题思路1：

不创建头结点，一 一遍历两个链表，将较小的值拿下来尾插，然后迭代下去，直至其中一个链表为空，然后把另外一个链表剩下的结点全部链接。但是要注意考虑头为NULL的特殊情况。

具体代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode* head=NULL; struct ListNode* tail=NULL; if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } while(list1 && list2) { if(list1->val < list2->val) { if(head==NULL) { tail=head=list1; } else { tail->next=list1; tail=tail->next; } list1=list1->next; } else { if(head==NULL) { tail=head=list2; } else { tail->next=list2; tail=tail->next; } list2=list2->next; } } if(list1) { tail->next=list1; } if(list2) { tail->next=list2; } return head; }

结果展示：

0bdb1be678f241d8832533ca1c3b9977.png

 解题思路2：

创建一个头结点，不存储数据，方法与第一种类似，但是不需要考虑头为NULL的情况。

具体代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } struct ListNode* head=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* tail=head; while(list1 && list2) { if(list1->val < list2->val) { tail->next=list1; tail=tail->next; list1=list1->next; } else { tail->next=list2; tail=tail->next; list2=list2->next; } } if(list1) { tail->next=list1; } if(list2) { tail->next=list2; } struct ListNode* first=head->next; free(head); return first; }

结果展示：

a682a31fc44f4accbc1419d467866ff9.png

 这两种方法都是可行的，我个人更喜欢第二种方法。

6 链表分割

题目描述：

d52f2d30b26b4ae6bef4b4fd7e5ebe17.png

解题思路：

创建两个头结点分别连接=x的链表，最后将较小链表的尾连接到大链表的头的下一位，最后别忘了给大链表的尾置NULL。

 848e4d452f114bc69d5b8caf6eef8dc9.png

具体代码：

class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here ListNode*headSmall=(ListNode*)malloc(sizeof(ListNode)); ListNode*tailSmall=headSmall; ListNode*headBig=(ListNode*)malloc(sizeof(ListNode)); ListNode*tailBig=headBig; ListNode*cur=pHead; while(cur) { if(cur->val < x) { tailSmall->next=cur; tailSmall=cur; } else { tailBig->next=cur; tailBig=cur; } cur=cur->next; } tailSmall->next=headBig->next; tailBig->next=NULL; return headSmall->next; } };

 

 结果展示：

cce15d7099d345dfb46fe44142122656.png

 

7 链表的回文结构

题目描述：

f7b7666852d7418f80ca77778c9e127c.png

 解题思路：

将链表看作两部分，前半部分和后半部分，再将后半部分逆置一一与前半部分比较，若相等就返回true,否则返回false.这里就不需要将前半部分的尾置为NULL。

具体代码：

struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow=head; struct ListNode* quick=head; while(quick && quick->next) { slow=slow->next; quick=quick->next->next; } return slow; } struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur=head; struct ListNode* newhead=NULL; while(cur) { struct ListNode* next=cur->next; cur->next=newhead; newhead=cur; cur=next; } return newhead; } class PalindromeList { public: bool chkPalindrome(ListNode* A) { // write code here ListNode* mid=NULL; mid=middleNode(A); ListNode* reverse=reverseList(mid); while(A && reverse) { if(A->val != reverse->val) { return false; } A=A->next; reverse=reverse->next; } return true; } };

 结果展示：

afdac51315c8424e9e3a035b2bf1aab9.png

 

8 相交链表

题目描述：

48361ec77b2c49a89db81eefce163214.png

 解题思路：

常规思路是遍历其中一个链表，再将该链表与另外一个链表中每个结点比较，这样做时间复杂度为O(N^2),显然是不符合题意的。较为优的解题思路是先判断链表是否相交，然后求链表长度差值，让较长的链表先走差值步，再同时走，直到两个结点相等。

 具体代码：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *tailA=headA,*tailB=headB; int lenA=1; int lenB=1; while(tailA->next) { lenA++; tailA=tailA->next; } while(tailB->next) { lenB++; tailB=tailB->next; } if(tailA!=tailB) { return NULL; } int dis=fabs(lenA-lenB); struct ListNode *small=headB; struct ListNode *big=headA; if(lenAnext; } while(big!=small) { big=big->next; small=small->next; } return small; }

结果展示：

cfd00ad2dcde4750bc3f36758b836e33.png

 

9 环形链表

题目描述：

7df9d9dae6bf45d092b0ca1116cb56d8.png

 解题思路：

定义两个快慢指针，让慢指针一次走一步，快指针一次走两步，当快指针等于慢指针时就返回true,否则返回false.

具体代码：

bool hasCycle(struct ListNode *head) { struct ListNode* slow=head; struct ListNode* fast=head; while(fast && fast->next) { slow=slow->next; fast=fast->next->next; if(fast==slow) { return true; } } return false; }

结果展示：

121e38cc89474ea58a6f5c28ed9c2a75.png

 题后深究：

1 slow一次走一步，fast一次走两步，他们一定会相遇吗？

2 若是slow一次走一步，fast一次走三步会怎样？fast一次走4步会怎样？

 

 063e102e7b194f248892e38bd20eaea3.png

假设slow刚进环时slow与fast之间的距离为X，由于fast每次都比slow快一步，所以他们之间的相对距离在以1之间减少，所以肯定会相遇。

如果fast一次走三步，当X为偶数时，他们一定相遇，当X为奇数时fast肯定在某个情况会恰好超过slow一位，这个时候他们能否相遇取决于C-1的奇偶情况（C表示环的长度），当C-1为奇数时永远不会相遇，当C-1为偶数时会相遇。

a2a0487f18d14548b0b10e971f496db3.png

 当fast一次走四步时也是同样的分析方法。

10 环形链表

题目描述：

d20ef29499144800b057c9a39a8a67e9.png

解题思路：

一个指针从相遇点开始走，一个指针从表头开始走，它们会在环的入口点相遇。

 代码实现：

struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *slow=head; struct ListNode *fast=head; struct ListNode *meetCode=NULL; while(fast && fast->next) { slow=slow->next; fast=fast->next->next; if(fast==slow) { meetCode=fast; slow=head; while(slow!=meetCode) { slow=slow->next; meetCode=meetCode->next; } return slow; } } return NULL; }

结果展示：

d2713ff5a7624d3fa93d8a45e99e449f.png

 题后深究：

为什么一个指针从相遇点开始走，一个指针从表头开始走，它们会在环的入口点相遇？

07a77c8cce3e4b36ada6adad6e9a502d.png

 由图中公式可知，上述结论是成立的。

 



【本文地址】


今日新闻

推荐新闻

CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3