链表相关OJ

1、移除链表元素

（1）题目描述

（2）算法原理

2、链表的中间结点

（1）题目描述

（2）算法原理

3、链表中倒数第K个结点

（1）题目描述

（2）算法原理

4、反转链表

（1）题目描述

（2）算法原理

5、合并两个有序链表

（1）题目描述

（2）算法原理

6、分割链表

（1）题目描述

（2）算法原理

7、回文链表

（1）题目描述

（2）算法原理

8、链表相交

（1）题目描述

（2）算法原理

9、环形链表

（1）题目描述

（2）算法原理

10、环形链表ll

（1）题目描述

（2）算法原理

1、移除链表元素

203. 移除链表元素 - 力扣（LeetCode）

（1）题目描述

（2）算法原理

解法一：尾插到新链表

当我们看到这道题的时候，我相信大多数人脑海中的第一个想法就是直接尾插到一个新链表当中。因此，我们可以遍历这个链表，如果当前节点的val不是要删除的数，就将它尾插到新链表，最后返回新链表的头。

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution 
{
public:ListNode* removeElements(ListNode* head, int val) {if(head == nullptr)return nullptr;ListNode* newhead = nullptr, *tail = nullptr;ListNode* cur = head;while(cur){//如果不是要删除的val,就尾插if(cur->val != val){//刚开始newhead为空，需要特殊处理。if(newhead == nullptr){newhead = tail = cur;}//尾插else {tail->next = cur;tail = tail->next;}}cur = cur->next;}if(tail)tail->next = nullptr;return newhead;}
};

这个地方还是有细节需要注意的，在最后需要把tail的next置为空。这里tail是有可能为空的，如果为空的话就会报错。因此需要特判一下。比如说题目给的示例3，链表里的数全是7，要删除的也全是7，此时就不会进入尾插的逻辑，tail就是空的。

这种做法是可以解决这道题的，但是毕竟不是真正的删除。因此接下来我们考虑一下如何在原链表上进行删除。

解法二：双指针

我们先看用一个指针行不行，肯定是不行的，因为你需要更改链接关系，还要删除，一个指针肯定是不行的，因此我们需要一个前驱指针，帮助我们修改链接关系。

开始的时候让prev为空，cur为头节点，然后遍历链表，如果cur节点的值不是要删除的值，就让prev更新为cur，cur=cur->next。否则说明cur节点的值是要删除的值，此时直接更新prev的指向关系，让prev的next指向cur的next,然后删除cur，在把cur更新为prev的next，prev和cur始终保持以前一后的关系。这里要注意一种情况，就是说我一上来第一个节点就是要删除的，那么这个时候prev是空呀，那么就会出问题，因此要特殊处理prev为空的情况，如果为空，说明一上来就是要删除的节点，那么此时将head更新为cur的下一个节点，然后删除cur,再将cur更新为head即可。prev不用动。

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution 
{
public:ListNode* removeElements(ListNode* head, int val) {ListNode* prev = nullptr;ListNode* cur = head;while(cur){if(cur->val != val){prev = cur;cur = cur->next;}else {if(prev == nullptr){head = cur->next;delete cur;cur = head;}else{prev->next = cur->next;delete cur;cur = prev->next;}}}return head;}
};

2、链表的中间结点

876. 链表的中间结点 - 力扣（LeetCode）

（1）题目描述

（2）算法原理

解法一：暴力求解

这道题大多数人看到之后的第一想法就是，我先遍历一遍这个链表，统计一下节点个数，然后节点个数除以2，然后再遍历一遍链表，就可以得到答案。

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution 
{
public:ListNode* middleNode(ListNode* head) {int count = 0;ListNode* cur = head;while(cur){count++;cur = cur->next;}count /= 2;cur = head;while(count--){cur = cur->next;}return cur;}
};

解法二：快慢指针

但是这道题有一种非常优秀的解法就是快慢指针。就是搞fast,slow两个指针，一开始都指向头节点，然后fast一次都两步，slow一次走一步，当fast或者fast->next为空的时候，slow刚好就是中间节点。

节点个数为奇数时：

节点个数为偶数时：

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution 
{
public:ListNode* middleNode(ListNode* head) {ListNode* slow = head,  *fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}
};

3、链表中倒数第K个结点

链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

（1）题目描述

（2）算法原理

解法一：暴力求解

我们第一眼看到这道题的时候肯定是想着先遍历一遍链表，统计链表长度n，然后长度n减去k，之后从头开始走n-k步。这里要注意，链表长度是有可能小于k的，因此要注意处理一下这种情况。

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution 
{
public:ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {if(pListHead == nullptr)return nullptr;ListNode* cur = pListHead;int count = 0;while(cur){count++;cur = cur->next;}count -= k;if(count < 0)return nullptr;cur = pListHead;while(count--){cur = cur->next;}return cur;}
};

解法二：快慢指针

这道题可以直接用快慢指针，定义slow和fast两个指针，先让fast走k步，然后再让fast和slow同时往后走，当fast走到空的时候，slow就是倒数第K个节点。其实是很好理解的。我们假设链表长度为n，fast先走k步，意味着fast到链表n的距离是n - k，之后slow和fast同时往后走，当fast到达结尾的时候，走的了n-k步，因此slow也就走了n-k步。刚好就是倒数第k个节点的位置。

但是要注意，就是K可能超出了链表的长度。

代码：

class Solution 
{
public:ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {if(pListHead == nullptr)return nullptr;ListNode* fast = pListHead;ListNode* slow = pListHead;while(k--){if(fast)fast = fast->next;elsereturn nullptr;}while(fast){slow = slow->next;fast = fast->next;}return slow;}
};

4、反转链表

206. 反转链表 - 力扣（LeetCode）

（1）题目描述

（2）算法原理

解法一：头插到新链表

利用头插的思想，直接将原链表节点头插到新链表当中。

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution 
{
public:ListNode* reverseList(ListNode* head) {ListNode* newhead = nullptr;ListNode* cur = head;while(cur){ListNode* next = cur->next;cur->next = newhead;newhead = cur;cur = next;}return newhead;}
};

解法二：三指针

话不多说，直接上图

代码：

class Solution 
{
public:ListNode* reverseList(ListNode* head) {if(head == nullptr) return nullptr;ListNode* prev = nullptr;ListNode* cur = head;ListNode* next = head->next;while(cur){cur->next = prev;prev = cur;cur = next;if(next)next = next->next;        }return prev;}
};

5、合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

（1）题目描述

（2）算法原理

如果大家做过合并两个有序数组那道题的话，这道题的解法是类似。我们可以同时遍历这两个链表，将val小的尾插到新链表中。当一个链表遍历结束的时候结束循环，之后将另一个尾插到新链表中。

代码：

class Solution 
{
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1 == nullptr)return list2;if(list2 == nullptr)return list1;ListNode* newhead = nullptr;ListNode* tail = nullptr;while(list1 && list2){if(list1->val < list2->val){if(newhead == nullptr){newhead = tail = list1;}else{tail->next = list1;tail = tail->next;}list1 = list1->next;}else{if(newhead == nullptr){newhead = tail = list2;}else{tail->next = list2;tail = tail->next;}list2 = list2->next;}}//直接尾插即可。不需要whileif(list1){tail->next = list1;}if(list2){tail->next = list2;}return newhead;}
};

6、分割链表

面试题 02.04. 分割链表 - 力扣（LeetCode）

（1）题目描述

（2）算法原理

这道题的思路就是我们搞两个链表small和large，然后遍历原始链表，将小于x的尾插到small，然后大于x的尾插到large，之后把large连接到small后面。这道题最后搞个哨兵位的头结点，写代码的时候就不用处理特殊情况了

代码：

class Solution 
{
public:ListNode* partition(ListNode* head, int x) {ListNode* small = new ListNode(0);ListNode* smallHead = small;ListNode* large = new ListNode(0);ListNode* largeHead = large;while (head != nullptr) {if (head->val < x) {small->next = head;small = small->next;} else {large->next = head;large = large->next;}head = head->next;}large->next = nullptr;small->next = largeHead->next;return smallHead->next;}
};

7、回文链表

LCR 027. 回文链表 - 力扣（LeetCode）

（1）题目描述

（2）算法原理

解法一：利用数组+双指针：

当我们看到这道题的时候，我头脑中的第一个想法就是遍历一遍链表，然后把节点的值存到数组里，然后定义两个指针，判断是不是回文。

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution 
{
public:bool isPalindrome(ListNode* head) {vector<int> v;ListNode* cur = head;while(cur){v.push_back(cur->val);cur = cur->next;}int left = 0, right = v.size() - 1;while(left < right){if(v[left] != v[right])return false;left++;right--;}return true;}
}

解法二：中间节点+反转链表

第一种解法是可以通过的，但是，有点取巧，有没有更优秀的解法呢？我们可以先找到链表的中间节点，然后将链表的后半部分逆置，然后比较前半部分链表和后半部分是否相同。其实就是我们做过的链表的中间节点和反转链表的一个融合。copy一下上两道题的代码。

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {if(head == nullptr) return nullptr;ListNode* prev = nullptr;ListNode* cur = head;ListNode* next = head->next;while(cur){cur->next = prev;prev = cur;cur = next;if(next)next = next->next;}return prev;}ListNode* middleNode(ListNode* head) {ListNode* fast = head, *slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}bool isPalindrome(ListNode* head) {ListNode* mid = middleNode(head);ListNode* rhead = reverseList(mid);while(rhead){if(head->val != rhead->val)return false;rhead = rhead->next;head = head->next;}return true;}
};

8、链表相交

（1）题目描述

（2）算法原理

通过观察不难发现我们可以遍历一下链表A和链表B的长度，然后让记录链表A和链表B的长度，之后让长的链表先走差距步，在同时走，如果有相同的节点就说明链表是有交点的。这里要注意不能比值，而要比地址。

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution 
{
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headA == nullptr || headB == nullptr)return nullptr;int len1 = 0, len2 =0;ListNode* cur1 = headA;ListNode* cur2 = headB;//求出链表长度while(cur1){len1++;cur1 = cur1->next;}while(cur2){len2++;cur2 = cur2->next;}//差距步int gap = abs(len1 - len2);//假设headA长ListNode* longg = headA;ListNode* shout = headB;if(len1 < len2){//说明假设错了，更改一下longg = headB;shout = headA;}while(gap--) //长的链表走差距步{longg = longg->next;}while(longg != shout){longg =longg->next;shout = shout->next;}return longg;}
};

9、环形链表

141. 环形链表 - 力扣（LeetCode）

（1）题目描述

（2）算法原理

先说结论，这道题要用快慢指针。定义slow和fast两个指针，让slow每次走一步，fast每次走两步，如果是环形链表，则一定会有slow==fast。那么问题就来了。

1、为什么slow走一步，fast走两步它们两个会相遇，会不会错过呢？

2、如果slow走1步，fast走n步(n>2)，它们两个会相遇? 会错过?

当n为3的时候其实就看距离是奇数还是偶数了,n为4的时候看距离是不是3的倍数，以此类推。

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution 
{
public:bool hasCycle(ListNode *head) {ListNode* slow = head;ListNode* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast)return true;}return false;}
};

10、环形链表ll

142. 环形链表 II - 力扣（LeetCode）

（1）题目描述

（2）算法原理

解法一：快慢指针

这道题让我们返回入环时候的第一个点，这道题肯定是和上一道题是有关联的。我们同样可以用快慢指针，和上一道题一样，求出fast和slow的相遇点，然后在用一个指针从头出发，另一个指针从相遇点出发，当它们的第一个地址相同的节点就是入环的第一个点。同样的我们来证明一下。

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution 
{
public:ListNode *detectCycle(ListNode *head) {ListNode* slow, *fast;slow = fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){ListNode* meet = slow;while(meet != head){meet = meet->next;head = head->next;}return meet;}}return nullptr;}
};

解法二：转换成链表相交

如果解法一大家有些迷惑，我们可以把它转换成链表相交。同样的，利用快慢指针，找到fast和slow的相遇点，然后将相遇点和相遇点下一个节点断开。然后其实就是两个链表找交点的问题了。

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*//*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headA == nullptr || headB == nullptr)return nullptr;int len1 = 0, len2 =0;ListNode* cur1 = headA;ListNode* cur2 = headB;//求出链表长度while(cur1){len1++;cur1 = cur1->next;}while(cur2){len2++;cur2 = cur2->next;}//差距步int gap = abs(len1 - len2);//假设headA长ListNode* longg = headA;ListNode* shout = headB;if(len1 < len2){//说明假设错了，更改一下longg = headB;shout = headA;}while(gap--) //长的链表走差距步{longg = longg->next;}while(longg != shout){longg =longg->next;shout = shout->next;}return longg;}
class Solution 
{
public:ListNode *detectCycle(ListNode *head) {ListNode* fast , *slow;fast = slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){ListNode* meet = slow;ListNode* next = meet->next;meet->next = nullptr;ListNode* cur = head;return getIntersectionNode(next,cur);}}return nullptr;}
};