链表经典OJ题合集（包含带环问题，相交问题，随机指针复制等，附动画讲解）

目录

一：前言

二：简单题目

(1)移除链表元素

(2)反转链表

(3)找链表的中间结点

(4)输入一个链表，输出该链表中倒数第k个结点

(5)合并两个有序链表

(6)相交链表

(7)判断链表是否带环

三：较难题目

(1)链表分割

(2)判断链表是否为回文结构

(3)找到成环链表的入环结点

(4)复制带随机指针的链表

---

一：前言

这一部分链表的OJ的题目适用于已经掌握链表基础的同学。

如果有对链表基础功能实现有问题的同学可以看这里：

https://blog.csdn.net/2301_76269963/article/details/129586021?spm=1001.2014.3001.5501

二：简单题目

(1)移除链表元素

链接：https://leetcode.cn/problems/remove-linked-list-elements/description/

题目要求：

🤓基础思路：

【1】特殊情况：链表为空直接返回NULL。

【2】使用一个cur指针遍历整个链表。

【3】涉及到释放结点，要提前用next指针记录下一个位置。

【4】 用prev记录要删除的结点的前一个结点，保证链表连通。

【5】如果要删除，prev不变；不用删除的话prev，next，cur都要迭代。

【6】如果删除的是头结点，头结点要进行迭代。

代码：

struct ListNode* removeElements(struct ListNode* head, int val) {//如果链表为空，直接返回NULL。if (head == NULL){return head;}//当前结点struct ListNode* cur = head;//记录下一个结点struct ListNode* next = head->next;//记录原结点struct ListNode* prev = head;while (cur){//如果找到要删除的结点if ((cur->val) == val){//如果释放的是头结点if (cur == head){free(cur);head = next;cur = next;}//释放的不是头结点else{free(cur);prev->next = next;}}//没找到进行prev迭代else{prev = cur;}//迭代，要考虑next已经为空的情况cur = next;if (next)next = next->next;}//返回头结点return head;
}

(2)反转链表

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

题目要求：

 🤓基础思路：

【1】建立一个新的头。

【2】将原链表中的元素一个个拿下来。

【3】用prev记录新链表前一个结点，然后让新拿下来的结点指向prev。

图解：

 代码：

struct listnode* reverselist(struct listnode* head){//一个个拿出来链接struct listnode* newnode = head;//记录前一个指针struct listnode* prev = NULL;while (head){//head指向后一个结点head = head->next;//改变结点指向newnode->next = prev;prev = newnode;//newnode要作为新的头结点，不能指空if (head)newnode = head;}return newnode;
}

(3)找链表的中间结点

链接：https://leetcode.cn/problems/middle-of-the-linked-list/description/

题目要求：

  🤓基础思路：

【1】设置一个慢指针slow和一个快指针fast。

【2】慢指针slow走一步，快指针fast走两步。

【3】当fast为空或者fast->next（避免对空指针解引用）为空就结束循环。

图解：

 代码：

struct ListNode* middleNode(struct ListNode* head){//慢指针struct ListNode* slow = head;//快指针struct ListNode* fast = head;while (fast){//如果是偶数个结点，fast为最后一个时应该直接跳出if (fast->next == NULL)break;fast = fast->next->next;slow = slow->next;}//返回慢结点return slow;
}

(4)输入一个链表，输出该链表中倒数第k个结点

链接：https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

题目要求：

 🤓基础思路：

【1】考虑特殊情况：链表为空，返回空；给的k值大于链表结点数，返回空。

【2】还是利用快慢指针，快指针先走k步，然后快慢指针相同速度走，直到快指针为空，此时慢指针就是要求的结点。

代码：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {//如果为空链表直接返回空 if (pListHead == NULL)return NULL;struct ListNode* slow = pListHead;struct ListNode* fast = pListHead;//快指针先走k步for (int i = 0; i < k; i++){if (fast == NULL)return NULL;fast = fast->next;}//慢指针会一直落后k个结点while (fast){fast = fast->next;slow = slow->next;}//返回慢指针return slow;
}

(5)合并两个有序链表

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

题目要求：

 🤓基础思路：

【1】考虑特殊情况：其中一个链表为空返回另一个链表。

【2】设置一个新头newhead和新尾newtail。

【3】依次比较链表结点，小的拿下来作为新尾。（相同情况拿第一个链表）

【4】其中一个链表走空结束循环，将没走完的链表的剩余结点链接到新链表后面。

图解：

代码： 

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{//设置一个新的头和新的尾struct ListNode* newhead = NULL, * newtail = NULL;//如果其中一个链表为空，返回另一个链表if (list1 == NULL)return list2;if (list2 == NULL)return list1;//如果第一个链表的结点数据大于第二个链表结点数据，//那第二个链表的头结点作为新头，反之第一个链表头结点作为新头if (list1->val >= list2->val){newhead = newtail = list2;list2 = list2->next;}else{newhead = newtail = list1;list1 = list1->next;}//一直循环，直到一边为空while (list1 && list2){//如果第一个链表的结点数据小，把这个结点接到新链表后面//然后进行迭代，指向下一个结点if (list1->val <= list2->val){newtail->next = list1;newtail = list1;list1 = list1->next;}//如果第二个链表的结点数据小，把这个结点接到新链表后面//然后进行迭代，指向下一个结点else{newtail->next = list2;newtail = list2;list2 = list2->next;}}//将没走到的链表的后续结点链接到新链表后面if (list1)newtail->next = list1;elsenewtail->next = list2;//返回新链表头return newhead;
}

(6)相交链表

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

题目要求：

 • 这个题目最好想到的方法就是暴力求解，将其中一个链表的每一个结点与另一个链表的每一个结点比较，如果存储的地址相同，说明下一个结点是相交结点，这样就利用了双重循环，时间复杂度到达了O(n^2),我运行的时候没通过，下面我们介绍一种时间复杂度为O（n）,思路相对简单的方法。

🤓基础思路：

【1】考虑特殊情况：其中一个链表为空，返回空。

【2】易知当两个非空链表相交时，两个链表的尾结点一定是相交结点，我们可以利用尾结点，判断两者是否相交。

【3】在找尾结点的同时计算两个链表的步长，计算距离差距gap，让长链表先走gap步，然后两个链表一起走，直到找到地址相同的结点（即交点）。

图解：

 代码：

struct listnode* getintersectionnode(struct listnode* heada, struct listnode* headb) {//计算长度int lengtha = 1;int lengthb = 1;//如果其中一个为空，返回空if (heada == null || headb == null)return null;//找两个链表的尾结点并计算长度struct listnode* taila = heada;struct listnode* tailb = headb;while (taila->next){taila = taila->next;lengtha++;}while (tailb->next){tailb = tailb->next;lengthb++;}//判断相交if (taila != tailb){return null;}//计算相差步长，abs函数可以算两数的绝对值int gap = abs(lengthb - lengtha);//设B链表长，A链表短struct listnode* longlist = headb;struct listnode* shortlist = heada;//如果A链表长，改变值if (lengtha > lengthb){shortlist = headb;longlist = heada;}//长链表先走gap步while (gap--){longlist = longlist->next;}//循环求两个链表交点while (longlist != shortlist){longlist = longlist->next;shortlist = shortlist->next;}//返回交点return longlist;
}

(7)判断链表是否带环

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

题目要求：

•在讲述基础思路前，我想先进行一个数学推导，如果有一个环形赛道，其中一个人A以速度2m/s跑，一个人B以速度1m/s跑 ,请问A是否能追上B？

很明显A一定会追上B，就像链表成环一样，两步走的一方一定会在环内部追上一步走的一方（链表的环长一定是正整数）。

图解：

  🤓基础思路：

【1】考虑特殊情况：链表为空，返回空。

【2】设置一个慢指针slow和快指针fast,慢走一步，快走两步。

【3】如果fast或者fast->next为空,说明链表不成环。

【4】如果成环，fast一定会追上slow，追上了返回true。

图解：

代码：

bool hasCycle(struct ListNode* head)
{struct ListNode* slow = head, * fast = head;//如果链表为空，返回falseif (head == NULL)return false;while (fast->next){//慢指针走一步，快走两步slow = slow->next;fast = fast->next->next;//如果走完直接为空，返回falseif (fast == NULL)return false;//如果fast追到slow,说明链表成环，返回true。if (fast == slow)return true;}//如果fast->next为空，链表不成环，返回false。return false;
}

三：较难题目

(1)链表分割

链接：https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

题目要求：

  🤓基础思路：

【1】设计一个cur指针遍历链表。

【2】将链表分割成两个链表，数据小于x的结点合成一个链表（简称小链表），数据大于x的合成一个链表（简称大链表）。

【3】考虑特殊情况：链表为空返回空，分割处理后如果其中一个链表为空，返回另一个链表。

【4】分割结束后小链表的尾要和大链表的头链接，大链表的尾要指向空。

图解： 

代码：

struct listnode* partition(struct listnode* head, int x) 
{//如果给的链表为空，我们直接返回空if (head == NULL)return NULL;//用来遍历整个链表struct listnode* cur = head;//小于x的链表struct listnode* lesshead = NULL;struct listnode* lesstail = NULL;//大于等于x的链表struct listnode* biggerhead = NULL;struct listnode* biggertail = NULL;//遍历整个链表while (cur){if (cur->val < x){//小于x的链表的第一个结点的插入if (lesshead == NULL){lesshead = lesstail = cur;}else{   //让原来的尾指向新尾lesstail->next = cur;lesstail = cur;}}else{//小于x的链表的第一个结点的插入if (biggerhead == NULL){biggerhead = biggertail = cur;}else{//让原来的尾指向新尾biggertail->next = cur;biggertail = cur;}}//cur迭代cur = cur->next;}//小链表的尾指向大链表头，大链表尾指空。//如果其中一个链表为空，不对其解引用if (lesstail != NULL)lesstail->next = biggerhead;if (biggertail != NULL)biggertail->next = NULL;//如果没有元素小于x,返回大的链表if (lesstail == NULL)return biggerhead;//如果没有元素大于x,返回小的链表elsereturn lesshead;
}

(2)判断链表是否为回文结构

链接：https://leetcode.cn/problems/aMhZSa/

题目要求：

 🤓基础思路：

【1】先找到中间的结点。（前面有）

【2】反转中间结点后的链表。（前面有）

【3】遍历两个链表，依次比较，有不同返回false。

【4】循环结束条件为两个链表任意一个走到空。

图解：

代码：

//判断链表是否为回文
//找中间结点
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow = head;struct ListNode* fast = head;while (fast){if (fast->next == NULL)break;fast = fast->next->next;slow = slow->next;}return slow;
}
//进行反转
struct ListNode* reverseList(struct ListNode* phead)
{struct ListNode* newnode = phead;//记录前一个指针struct ListNode* prev = NULL;while (phead){//head指向后一个结点phead = phead->next;//改变结点指向newnode->next = prev;prev = newnode;//newnode要作为新的头结点，不能指空if (phead)newnode = phead;}return newnode;
}
//判断是否为回文
bool isPalindrome(struct ListNode* head) 
{//找中间struct ListNode* mid = middleNode(head);//反转struct ListNode* rHead = reverseList(mid);//前半段struct ListNode* cur1 = head;//后半段struct ListNode* curA = rHead;//一个个判断，不同直接返回falsewhile (cur1 && curA){if (cur1->val != curA->val){return false;}else{//如果相同，迭代cur1 = cur1->next;curA = curA->next;}}//全部相同，返回true。return true;
}

(3)找到成环链表的入环结点

链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/

题目要求：

 题目的两种思路：

1.相遇后断开

🤓基础思路：

【1】设计快慢指针，快走两步，慢走一步，找到第一次相遇的结点（简称meet）。

【2】在这个结点处断开，meet指向空，meet原来的下一个结点作为新链表的头。

【3】题目就转换为了求两个链表的交点。

图解：

代码：

//第二解法，断开找交点
struct ListNode* detectCycle(struct ListNode* head)
{struct ListNode* slow = head, * fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;//相遇if (fast == slow){struct ListNode* meet = fast;//第二个链表的头struct ListNode* newhead = fast->next;fast->next = NULL;//找到交点struct ListNode* headTail = head;struct ListNode* newheadTail = newhead;//计算长度int len = 0;int newLen = 0;while (headTail){headTail = headTail->next;len++;}while (newheadTail){newheadTail = newheadTail->next;newLen++;}//计算长度差距int gap = abs(newLen - len);struct ListNode* longList = newhead;struct ListNode* shortList = head;if (len > newLen){longList = head;shortList = newhead;}//长链表先走gap步while (gap--){longList = longList->next;}while (longList != shortList){longList = longList->next;shortList = shortList->next;}//返回交点return longList;}}//走到空返回NULLreturn NULL;
}

 2.数学公式法（更加简洁）

🤓基础思路：

【1】先进行数学推导。

【2】将公式转换成代码。

推导：

代码：

//判断是否成环并且找到入环点
struct ListNode* detectCycle(struct ListNode* head) 
{//判断是否有环struct ListNode* fast = head, * slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;//相遇if (fast == slow){//公式法struct ListNode* meet = slow;while (head != meet){head = head->next;meet = meet->next;}return meet;}}//没有成环，返回空。return NULL;
}

(4)复制带随机指针的链表

链接：https://leetcode.cn/problems/copy-list-with-random-pointer/description/

题目要求：

 🤓基础思路：

【1】考虑特殊情况：链表为空，返回空。

【2】我们可以依次复制链表中的结点并将它们放在原链表结点之后。

图解：

★★★链接之后我们可以发现一个非常神奇的规律，那就是除了random指向NULL的情况，其它新生成结点的random都是它前一个结点的random的next。 

【3】根据规律复制random

【4】合成新链表，恢复原链表。

图解：

代码：

struct node* copyrandomlist(struct node* head) 
{//如果链表为空。返回空if (head == NULL)return NULL;//复制加链接struct node* cur = head;while (cur){//生成新结点struct node* copy = (struct node*)malloc(sizeof(struct node));//复制数据域copy->val = cur->val;//复制指针域copy->next = cur->next;//链接两个链表cur->next = copy;//迭代cur = copy->next;}//复制randomcur = head;while (cur){struct node* copy = cur->next;//cur->random为空的情况单独处理if (cur->random == NULL)copy->random = NULL;else{copy->random = cur->random->next;}//迭代cur = copy->next;}//切割复原cur = head;//新链表的头和尾struct node* copyhead = cur->next;struct node* copytail = cur->next;while (cur != NULL){//恢复原链表结构cur->next = copytail->next;//cur迭代cur = cur->next;//如果cur为空，不进行迭代if (cur ){//旧尾指向新尾copytail->next = cur->next;//迭代copytail = copytail->next;}}//返回新链表的头return copyhead;
}