数据结构之链表OJ练习检验你的链表水平是否合格

转x33g5p2x  于2021-11-24 转载在 其他  
字(21.9k)|赞(0)|评价(0)|浏览(358)

1.反转链表

K个一组翻转链表

链表的中间节点：

链表倒数第k个节点：

删除链表倒数第k个节点：

合并两个有序链表：

链表插入排序：

链表排序：

删除链表的节点：

删除链表的节点II：

​环形链表（重点面试常考）

环形链表Il（重点面试常考）

分割链表：

回文链表：

链表相交：

1.反转链表

对应letecode链接：
力扣

https://leetcode-cn.com/problems/UHnkqh/

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

注意：本题与主站 206 题相同： https://leetcode-cn.com/problems/reverse-linked-list/

解题分析： 方法1，双指针法:

设置两个链表：ans 表示已经被反转的链表, head 表示还未被反转的链表。
遍历链表，每次将未被反转的链表 head 的 首元节点反转，直至未被反转的链表为空。 


​

对应代码：

  1. class Solution {
  2. public:
  3.     ListNode* reverseList(ListNode* head) {
  4.             ListNode*ans=nullptr;
  5.             while(head){
  6.                 ListNode*restList =head->next;//保存head的下一个节点
  7.                 head->next=ans;//翻转指针
  8.                 ans=head;//迭代
  9.                 head=restList;
  10.             }
  11.             return ans;
  12.     }
  13. };

运行结果：

方法二：递归

思想与上面的思想大致相同，翻指针：
1.使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 ret .
2.此后，每次函数在返回的过程中，让当前结点的下一个结点的 next->next 指针指向当前节点。
3.同时让当前结点的 next->next 指针指向 NULL ，从而实现从链表尾部开始的局部反转
4.当递归函数全部出栈后，链表反转完成。

图解：


​

对应代码：

  1. class Solution {
  2. public:
  3.     ListNode* reverseList(ListNode* head) {
  4.              if(!head||!head->next)return head;
  5.              ListNode*ret=reverseList(head->next);
  6.              head->next->next=head;
  7.              head->next=nullptr;
  8.              return ret;
  9.     }
  10. };

方法三：头插法

1.原链表的头结点就是反转之后链表的尾结点，使用 head 标记 .
2.定义指针 cur，初始化为 head .
3.每次都让 head 下一个结点的 next 指向 cur ，实现一次局部反转
4.局部反转完成之后，cur和 head 的 next 指针同时 往前移动一个位置
5.循环上述过程，直至 cur 到达链表的最后一个结点 。


​

对应代码：

  1. class Solution {
  2. public:
  3.     ListNode* reverseList(ListNode* head) {
  4.         if (head == NULL) { return NULL; }
  5.         ListNode* cur = head;
  6.         while (head->next != NULL) {
  7.             ListNode* t = head->next->next;
  8.             head->next->next = cur;
  9.             cur = head->next;
  10.             head->next = t;
  11.         }
  12.         return cur;
  13.     }
  14. };

递归写法太复杂在这里就不写了：

K个一组翻转链表

对应letecode链接：
25. K 个一组翻转链表 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
示例 3：

输入：head = [1,2,3,4,5], k = 1
输出：[1,2,3,4,5]
示例 4：

输入：head = [1], k = 1
输出：[1]
提示：

列表中节点的数量在范围 sz 内
1 <= sz <= 5000
0 <= Node.val <= 1000
1 <= k <= sz

相信有了上面那两道题的基础这道题就每这么难了：

解题思路：
我们需要把链表节点按照 k 个一组分组，所以可以使用一个指针 head 依次指向每组的头节点。这个指针每次向前移动 k 步，直至链表结尾。对于每个分组，我们先判断它的长度是否大于等于 k。若是，我们就翻转这部分链表，否则不需要翻转。

接下来的问题就是如何翻转一个分组内的子链表。翻转一个链表并不难，过程可以参考上面的翻转链表。但是对于一个子链表，除了翻转其本身之外，还需要将子链表的头部与上一个子链表链接，以及子链表的尾部与下一个子链表链接。如下图所示：


​

对应代码：

翻转[head,tail）区间的链表：

  1. ListNode*Reverse(ListNode*head,ListNode*tail)//翻转区间[head,tail)不包括tail
  2. {
  3.             ListNode*cur=head;
  4.             ListNode*prev=nullptr;
  5.             while(cur!=tail){
  6.              ListNode*next=cur->next;
  7.                   cur->next=prev;
  8.                 prev=cur;
  9.                 cur=next;
  10.             }
  11.             return prev;
  12. }

总代码：

  1. class Solution {
  2. public:
  3. ListNode*Reverse(ListNode*head,ListNode*tail)//翻转区间[head,tail)不包括tail
  4. {
  5.             ListNode*cur=head;
  6.             ListNode*prev=nullptr;
  7.             while(cur!=tail){
  8.              ListNode*next=cur->next;
  9.                   cur->next=prev;
  10.                 prev=cur;
  11.                 cur=next;
  12.             }
  13.             return prev;
  14. }
  16.     ListNode* reverseKGroup(ListNode* head, int k) {
  17.              if(!head||!head->next)return head;//空或者只有一个元素了则返回
  19.             ListNode*tail=head;
  20.             for(int i=0;i<k;i++){
  21.                 if(!tail)//不足k个
  22.                 return head;
  23.                 tail=tail->next;
  24.             }
  26.             ListNode*newnode=Reverse(head,tail);//翻转每一组链表
  27.             head->next=reverseKGroup(tail,k);//翻转之后head已经变成了尾节点了
  29.              return newnode;//翻转完之后返回
  30.     }
  31. };

这道题和两两一组翻转链表是一样的：

对应链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs/https://leetcode-cn.com/problems/swap-nodes-in-pairs/

https://leetcode-cn.com/problems/swap-nodes-in-pairs/

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：

输入：head = []
输出：[]
示例 3：

输入：head = [1]
输出：[1]
 

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
 

进阶：你能在不修改链表节点值的情况下解决这个问题吗?（也就是说，仅修改节点本身。）

由于上图已经讲过思路在这里就不赘述了：

  1. class Solution {
  2. public:
  3. ListNode*Reverse(ListNode*head,ListNode*tail){
  4.       ListNode*cur=head;
  5.       ListNode*prev=nullptr;
  6.       while(cur!=tail){
  7.           ListNode*next=cur->next;
  8.          cur->next=prev;
  9.          prev=cur;
  10.          cur=next;
  11.       }
  12.       return prev;
  13. }
  15.     ListNode* swapPairs(ListNode* head) {
  16.           if(!head||!head->next)return head;
  17.           ListNode*tail=head;
  18.           for(int i=0;i<2;i++){
  19.               if(!tail)return head;
  20.               tail=tail->next;
  21.           }
  22.           ListNode*newnode=Reverse(head,tail);
  23.           head->next=swapPairs(tail);
  24.           return newnode;
  25.     }
  26. };

当然还可以采用另外一种递归方式：

1.递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。

2.如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换。

3.用 head 表示原始链表的头节点，新的链表的第二个节点，用 newHead 表示新的链表的头节点，原始链表的第二个节点，则原始链表中的其余节点的头节点是 newHead.next。令 head.next = swapPairs(newHead.next)，表示将其余节点进行两两交换，交换后的新的头节点为 head 的下一个节点。然后令 newHead.next = head，即完成了所有节点的交换。最后返回新的链表的头节点 newHead。

对应代码：

  1. class Solution {
  2. public:
  3.     ListNode* swapPairs(ListNode* head) {
  4.         if (head == nullptr || head->next == nullptr) {
  5.             return head;
  6.         }
  7.         ListNode* newHead = head->next;
  8.         head->next = swapPairs(newHead->next);
  9.         newHead->next = head;
  10.         return newHead;
  11.     }
  12. };

链表的中间节点：

对应letecode链接：
876. 链表的中间结点 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

给定链表的结点数介于 1 和 100 之间。

解题思路：快慢指针

1.用两个指针 slow 与 fast 一起遍历链表。

2.slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间位置。

3.注意链表的长度有可能是偶数或者奇数，所以循环结束的条件为fast!=nullptr&&fast->next!=nullptr;


​

对应代码：

  1. class Solution {
  2. public:
  3.     ListNode* middleNode(ListNode* head) {
  4.                ListNode*fast=head;
  5.                ListNode*slow=head;
  6.                while(fast&&fast->next){
  7.                    fast=fast->next->next;
  8.                    slow=slow->next;
  9.                }
  10.                return slow;
  11.     }
  12. };

提交结果：

l

链表倒数第k个节点：

对应letecode 链接：

题目描述：
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

解题思路：快慢指针

1.定义一个快指针先让它走k步

2.定义一个慢指针指向链表的头节点，此时和fast同时走。

3.结束条件,当fast走到空了就结束了，此时slow只是倒数第k个节点

对应代码：

  1. class Solution {
  2. public:
  3.     ListNode* getKthFromEnd(ListNode* head, int k) {
  4.             ListNode*fast=head;
  5.             for(int i=0;i<k;i++){
  6.                 if(fast)fast=fast=fast->next;//防止链表的长度不够走
  7.             }
  8.             ListNode*slow=head;
  9.             while(fast){
  10.                 fast=fast->next;//同时走
  11.                 slow=slow->next;
  12.             }
  13.             return slow;
  14.     }
  15. };

删除链表倒数第k个节点：

对应letecode链接：
剑指 Offer II 021. 删除链表的倒数第 n 个结点 - 力扣（LeetCode） (leetcode-cn.com)

解题思路：快慢指针

1.这题与上题思路大致相同，只是本题是要删除倒数第k个节点，而上题是只要我们找到倒数第k个节点。

2.同样的我们可以 定义fast,slow指针先让fast指针先走K+1部，在让slow和fast同时走但是，循环结束之后我们要删除的刚好是slow的位置，那么我们就必须知道slow的前一个让后在将slow指向的节点删除，返回头节点即可

但是如果我们考虑特殊情况：

考虑一种比较特殊的情况，若需要删除的就是头节点，这时候就存在 bug 。如上图中快指针先走了 6 步，这时候已经超出了尾节点，所以对于这种情况需要做 if 特殊判断。一种比较好的避免这种特殊判断的方法是引入哨兵节点 dummy，该结点的 next 指针指向头指针，之后这样处理以 dummy 为头结点的链表就可以规避上述问题，最后返回dummy 的 next 指针所指的链点就是需要的结果。以 3 个结点的链表处理删除头结点的情况为例子，如下图（红色节点为哨兵节点）

对应代码：

  1. class Solution {
  2. public:
  3.     ListNode* removeNthFromEnd(ListNode* head, int n) {
  4.           ListNode*dummyHead=new ListNode(-1);
  5.           dummyHead->next=head;
  6.           ListNode*fast=head;
  8.           for(int i=0;i<k;i++){//让快指针走k步
  9.               if(fast)fast=fast->next;
  10.           }
  11.           ListNode*slow=dummyHead;
  12.           while(fast){
  13.               fast=fast->next;
  14.               slow=slow->next;
  15.           }
  16.           ListNode*del=slow->next;
  17.           slow->next=slow->next->next;
  18.           delete del;//删除节点
  19.           ListNode*ans=dummyHead->next;//保存头节点
  20.           delete dummyHead;//释放哑节点
  21.           return ans;
  23.     }
  24. };

运行结果：

合并两个有序链表：

对应letecode链接：
21. 合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com)

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

题目描述：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

解题思路：

1.我们可以定义一个哑节点prevHead。

2.假设两个链表分别为l1,和l2，变量l1和l2，去它们之中小的那个尾插到哑节点（prevHead)后面，在将对应链表中的节点向后移一位 .

3.当循环结束之后l1和l2中有一个链表的节点取完了但是我们不知道是那一个节点走完了，但是我们可以都判断一个，将其链接到新链表的尾步即可。

4.同时我们还需要定义一个prev来记录新链表的头，代替哑节点走上述的过程

对应图解：

对应代码：

  1. class Solution {
  2. public:
  3.     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
  4.               ListNode*prevHead=new ListNode(-1);
  5.               ListNode*prev=prevHead;
  6.               while(l1&&l2){
  7.                   if(l1->val<=l2->val){
  8.                       prev->next=l1;
  9.                       prev=prev->next;
  10.                       l1=l1->next;
  11.                   }
  12.                   else{
  13.                       prev->next=l2;
  14.                       prev=prev->next;
  15.                       l2=l2->next;
  16.                   }
  17.               }
  18.               if(l1)prev->next=l1;
  19.               if(l2)prev->next=l2;
  20.               return prevHead->next;
  21.               
  22.     }
  23. };

运行结果：

 链表插入排序：

对应letecode链接：
力扣

https://leetcode-cn.com/problems/insertion-sort-list/

题目描述：

对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

示例 1：

输入: 4->2->1->3
输出: 1->2->3->4
示例 2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5

解题思路：

如果对插入排序不太理解的铁子，可以看一下我写的排序的博客

对应链接：

1.链表与数组的插入排序不同，数组支持随机访问。而链表是不支持随机访问的。我们在数组中可以随意的前后移动，将指针指向值和新元素的值比较后，将新元素插入到合适的位置。我们知道链表查询元素的时间复杂度为 O（n）,我们只能够通过遍历链表查询元素。那么我们怎么才能将新元素放到合适的位置呢？

此时我们不能通过移动绿色指针来寻找 5 的合适位置，那么我们应该怎么做了？

当我们发现绿色指针的值大于新元素时（7 > 5），我们则可以定义一个新指针，让其从哑节点开始遍历，直到找到新元素（5）的位置，（4 和 7 之间），然后再将新元素插入即可

通过上面的分析我们知道了大致过程，那么我们的是如何将新元素插入到指定位置的呢？

我们想要将 3 插入到 2 和 4 的中间，此时我们三个指针分别指向 2，4，3

我们共分 4 步，来完成这个操作，见下图

完成上述操作之后链表就变成了：

对应代码:

  1. class Solution {
  2. public:
  3.     ListNode* insertionSortList(ListNode* head) {
  4.           if(!head||!head->next)return head;//如果只有一个元素或者链表为空则返回head
  6.           ListNode*dummyNode=new ListNode(-1);//定义哑节点
  7.           dummyNode->next=head;
  8.           ListNode*prev=head->next;
  9.           ListNode*last=head;
  10.           ListNode*temphead=dummyNode;
  11.           while(prev){
  13.               if(last->val<=prev->val){
  14.                   last=last->next;
  15.                   prev=prev->next;
  16.                   continue;
  17.               }
  18.               temphead=dummyNode;
  20.               while(temphead->next->val<=prev->val){//比较找到对应的位置
  21.                   temphead=temphead->next;
  22.               }
  24.               //找到了对应的插入位置，如果不清除的老铁可以自己画一下图
  25.               last->next=prev->next;
  26.               prev->next=temphead->next;//链接
  27.               temphead->next=prev;
  28.               prev=last->next;//迭代往后走
  30.           }
  31.           return dummyNode->next;
  32.     }
  33. };

当然我们也可以不用头节点，但是那样就可以复杂一些：在这里就简单的改成代码不过多的解释：

链表排序：

对应letecode链接：
[Alton]-148-桶/归并 3 解 Java/C++ - 排序链表 - 力扣（LeetCode） (leetcode-cn.com)

https://leetcode-cn.com/problems/sort-list/

题目描述：

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：

输入：head = []
输出：[]

解题思路：归并排序

归并排序，逃脱不了，分合。 思路如下：

分割 -> 通过递归不断分割链表，在此过程中需要保证链表不丢失的情况下，不断想下切割 （e.g. 8 -> 4 -> 2）
关键在于找到链表的中心点， 并从中心点将链表分割成 2 部分。
我们可以使用经典的快慢双指针链表分割方法，其中有个点需要注意，链表长度为奇偶，切割处理方式是不同的，这里根据大家喜欢的方式处理即可，这里没有明确规定必须使用什么切割方式，笔者的切换策略如下：
快指针每次移动 2 步，慢指针每次移动 1​​ 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
找到中点后，将链表进行断开，将当前链表分成 2 部分
对两个链表分别排序
慢指针的下一节点，指向空即可
分割阶段结束 -> 递归退出 -> 直到分割的链表长度为 1
此时递归到底了
merge 环节，退出递归的过程中，不断的排序合并
merge 节点其实包含在分割阶段里边
merge -> 排序当前链表

对应代码：

分割代码：

  1. ListNode*splitListNode(ListNode*head){
  2.         if(!head||!head->next)return head;
  3.         ListNode*slow=head;
  4.         ListNode*fast=head;
  5.         ListNode*prev=nullptr;
  6.         while(fast&&fast->next){
  7.             prev=slow;
  8.             fast=fast->next->next;
  9.             slow=slow->next;
  10.         }
  12.         return prev;
  13.     }

注意中间那个节点要分给对二段链表：

如果只有两个节点的话，slow指向的就是第二个节点。如果将其分给第一个合并的链表那么就会死循环！！！！

合并链表：

  1. istNode*mergeListNode(ListNode*head1,ListNode*head2){
  2.             ListNode*dummyHead=new ListNode(-1);
  3.             ListNode*ans=dummyHead;
  4.               while(head1&&head2){
  5.                   if(head1->val<=head2->val){
  6.                       ans->next=head1;
  7.                       ans=ans->next;
  8.                       head1=head1->next;
  9.                   }
  10.                   else{
  11.                       ans->next=head2;
  12.                       ans=ans->next;
  13.                       head2=head2->next;
  14.                   }
  15.               }
  16.               if(head1)ans->next=head1;
  17.               if(head2)ans->next=head2;
  18.               return dummyHead->next;
  19.        }

由于上面的之前都已经讲解过了在这里就不重复了：

总代码：

  1. class Solution {
  2. public:
  3.     ListNode*splitListNode(ListNode*head){
  4.         if(!head||!head->next)return head;
  5.         ListNode*slow=head;
  6.         ListNode*fast=head;
  7.         ListNode*prev=nullptr;
  8.         while(fast&&fast->next){
  9.             prev=slow;
  10.             fast=fast->next->next;
  11.             slow=slow->next;
  12.         }
  14.         return prev;
  15.     }
  17.      ListNode*mergeListNode(ListNode*head1,ListNode*head2){
  18.             ListNode*dummyHead=new ListNode(-1);
  19.             ListNode*ans=dummyHead;
  20.               while(head1&&head2){
  21.                   if(head1->val<=head2->val){
  22.                       ans->next=head1;
  23.                       ans=ans->next;
  24.                       head1=head1->next;
  25.                   }
  26.                   else{
  27.                       ans->next=head2;
  28.                       ans=ans->next;
  29.                       head2=head2->next;
  30.                   }
  31.               }
  32.               if(head1)ans->next=head1;
  33.               if(head2)ans->next=head2;
  34.               return dummyHead->next;
  35.        }
  37.     ListNode* sortList(ListNode* head) {
  38.                if(!head||!head->next)return head;
  39.                ListNode*mid=splitListNode(head);
  40.                ListNode*midNext=mid->next;
  41.                mid->next=nullptr;
  42.                ListNode*head1=sortList(head);
  43.              ListNode*head2= sortList(midNext);
  44.           return mergeListNode(head1,head2);
  45.     }
  46.    
  47. };

运行结果：

当然这题还可以使用快速排序的前后指针法进行排序：

我们可以选取头节点作为基准值，遍历链表，将比它小的节点头插在它前面，比它大的节点尾插在它后面
假设lhead维护的是小于基准值的头插指针，utail维护的是大于等于基准值的尾插指针
则一次对[head , end）快排结束后有
-[ lhead , head ) （左闭右开）是小于基准值的一部分
-[ head.next , end ) （左闭右开）是大于等于基准值的一部分
再分治这两部分即可

对应代码:s

  1. class Solution {
  2. public:
  3.     ListNode* sortList(ListNode* head) {
  4.           return quickSortListNode(head,nullptr);
  5.     }
  6.     ListNode*quickSortListNode(ListNode*head,ListNode*end){
  7.                  if(head ==end || head->next ==end) return head;
  8.         ListNode* lhead = head ,*utail = head ,*p = head->next;
  9.         while (p != end){
  10.             ListNode *next = p->next;
  11.             if(p->val < head->val){//头插
  12.                 p->next = lhead;
  13.                 lhead = p;
  14.             }
  15.             else { //尾插
  16.                 utail->next = p;
  17.                 utail = p;
  18.             }
  19.             p = next;
  20.         }
  21.         utail->next = end;
  22.         ListNode *node = quickSortListNode(lhead, head);
  23.         head->next =  quickSortListNode(head->next, end);
  24.         return node;
  26.     }
  27. };

删除链表的节点：

对应letecode链接：
剑指 Offer 18. 删除链表的节点 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

解题思路：

题中说了链表中的节点值互不相同，也就是说最多只能删除一个。最简单的一种方式就是双指针求解，我们使用两个指针一个指向当前的节点，一个指向当前的上一个节点。

对应代码：

  1. class Solution {
  2. public:
  3.     ListNode* deleteNode(ListNode* head, int val) {
  4.        ListNode*dummyListNode=new ListNode(-1);
  5.        ListNode*prev=dummyListNode;
  6.         dummyListNode->next=head;
  7.          ListNode*cur=head;
  8.          while(cur){
  9.            if(cur->val==val){
  10.                prev->next=cur->next;//删除节点
  11.                cur=cur->next;
  12.                break;
  13.            }
  14.            else{
  15.                cur=cur->next;
  16.                prev=prev->next;//同时往后走
  17.            }
  18.          }
  19.          ListNode*ans=dummyListNode->next;//保存答案
  20.          delete dummyListNode;
  21.          return ans;
  22.     }
  23. };

对应运行结果：

删除链表的节点II：

对应letecode链接：
82. 删除排序链表中的重复元素 II - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排序

解题思路：

题目与上题的不同之处是，删除所有重复出现的元素。如示例所示，头结点是1，其后结点和其重复，因此也要删除。这时，用解决上题题的思路就不合适了。

因此，需要一个虚拟头结点，然后用变量prev指向该虚拟头结点。这样在删除重复结点之后，剩余的结点就可以挂在prev之后继续考察了。具体步骤我们一起看下。

为了方便演示，我将示例给出的链表删减如下：

然后变量difNode指向cur所指向的结点，用以记录和当前考察结点不同的结点位置。

变量curRepeatNum表示和变量cur指向的结点重复的结点个数，初始值为0

这时，变量cur和变量difNode指向的是同一个结点，因此curRepeatNum=1。

接着，将变量difNode向后移动一个位置，看下一个结点和变量cur指向的结点值是否相等。在这里，变量cur和变量difNode指向的结点值相等，因此curRepeatNum=2。

接着，将变量difNode继续向后移动一个位置，看下一个结点和变量cur指向的结点值是否相等。在这里，变量cur和变量difNode指向的结点值不相等。

时curRepeatNum=2，表示cur指向的结点1在链表中出现了2次。接着要做的是将变量prev指向的结点的后继指针指向变量difNode所指向的结点。这样，将就重复结点1从链表中删除了。

最后，要做的是将变量cur指向difNode所指向的结点，进行下一个结点的去重

对应代码：

  1. class Solution {
  2. public:
  3.     ListNode* deleteDuplicates(ListNode* head) {
  4.          ListNode*dummyHead=new ListNode(-1);
  5.          dummyHead->next=head;
  6.          ListNode*prev=dummyHead;
  7.          ListNode*cur=head;
  8.          while(cur){
  9.              int curRepeatNum=0;
  10.              ListNode*difNode=cur;// 找到和cur指向的结点值不同的结点
  11.              while(difNode&&difNode->val==cur->val){
  12.                   curRepeatNum++;
  13.                   difNode=difNode->next;
  14.              }
  15.              if(curRepeatNum>1){// 如果curRepeatNum的值大于1，则表示cur指向的结点重复出现了
  16.                  prev->next=difNode;
  17.              }
  18.              else{
  19.                  prev=cur;// cur指向的结点没有重复出现，则将变量prev指向cur所指向的结点
  20.              }
  21.              cur=difNode;
  22.          }
  23.          return dummyHead->next;
  24.     }
  25. };

运行结果：

环形链表（重点面试常考）

对应letecode链接：
141. 环形链表 - 力扣（LeetCode） (leetcode-cn.com)

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

题目描述：

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

解题思路：快慢指针：

最简单的一种方式就是快慢指针，慢指针每次走一步，快指针每次走两步，如果相遇就说明有环，如果有一个为空说明没有环。代码比较简单：

  1. class Solution {
  2. public:
  3.     bool hasCycle(ListNode *head) {
  4.         ListNode*fast=head;
  5.         ListNode*slow=head;
  6.         while(fast&&fast->next){
  7.             fast=fast->next->next;
  8.             slow=slow->next;
  9.             if(slow==fast)return true;
  10.         }
  11.         return false;
  12.     }
  14. };

但是如果这道题是在面试中就不会这么容易让你过，因为太简单：面试官一般都会问你为什么他们一定会相遇，fast每次只能走两步吗？一次走三步走四步行不行，或者走n步行不行

答案是fast每次走两步才能保证他们一定会相遇 待博主细细道来：
假如环的长度是m，快慢指针最近的间距是n，如图所示

快指针每次走两步，慢指针每次走一步，所以每走一次快慢指针的间距就要缩小一步，他们之间的间距没走一次缩小1步由于m,n都是整数那么迟早都会减到0.

在图一中当走n次的时候就会相遇，在图二中当走m-n次的时候就会相遇。

那如果fast每次走三步了？还会不会相遇了？答案是不一定？

还是一样的当slow进环之后，假设他们的间距为n,但是fast,slow每走一次距离会缩小2，此时如果n是偶数那么它们会相遇，如果是奇数，那么他们之间的距离会减到-1，-1代码什么意思了？-1代码fast反超slow此时他们之间的距离就变成了环的长度减1，也就是m-1，和上面的分析一样，如果m-1是偶数那么就可以相遇当时如果m-1是奇数那么它又会减到-1，那么就会重复上述步骤。那么他们也就永远不会相遇。

fast一次走四步的分析方法也是类似的，各位铁子可以自己下去推导

环形链表Il（重点面试常考）

对应letecode链接：
142. 环形链表 II - 力扣（LeetCode） (leetcode-cn.com)

对应题目描述：

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
 

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

解题思路：双指针

1.设slow fast 第一次相遇 。设两指针 fast，slow 指向链表头部 head，fast 每轮走 2 步，slow 每轮走 11步。

第一种情况：

fast 指针走过链表末端，说明链表无环，直接返回 null；

第二种情况：若有环，两指针一定会相遇。因为每走 1 轮，fast 与 slow 的间距 -1，fast 终会追上 slow

第三种情况：

当fast == slow时， 两指针在环中 第一次相遇 。下面分析此时fast 与 slow走过的 步数关系 ：

设链表共有 a+b 个节点，其中 链表头部到链表入口 有 a 个节点（不计链表入口节点）， 链表环 有 b 个节点（注意：a 和 b 是未知数，例如图解上链表 a=4 , b=5）。

设两指针分别走了 f，s 步，则有：
fast 走的步数是slow步数的 2 倍，即 f = 2s；（解析： fast 每轮走 2 步）
fast 比 slow多走了 n 个环的长度，即f=s+nb；（ 解析： 双指针都走过 a 步，然后在环内绕圈直到重合，重合时 fast 比 slow 多走 环的长度整数倍 ）；
以上两式相减得：

f = 2nb，s = nb，即fast和slow 指针分别走了 2n，n 个 环的周长 （注意： n 是未知数，不同链表的情况不同）。

如果让指针从链表头部一直向前走并统计步数k，那么所有 走到链表入口节点时的步数 是：k=a+nb（先走 a 步到入口节点，之后每绕 1 圈环（ b 步）都会再次到入口节点）。
而目前，slow 指针走过的步数为 nbnb 步。因此，我们只要想办法让 slow 再走 a 步停下来，就可以到环的入口。
但是我们不知道 a 的值，该怎么办？依然是使用双指针法。我们构建一个指针，此指针需要有以下性质：此指针和slow 一起向前走 a 步后，两者在入口节点重合。那么从哪里走到入口节点需要 a 步？答案是链表头部head。

双指针第二次相遇：

slow指针 位置不变 ，将fast指针重新 指向链表头部节点 ；slow和fast同时每轮向前走 1 步；
TIPS：此时 f = 0，s = nb ；
当 fast 指针走到f = a步时，slow 指针走到步s = a+nb，此时 两指针重合，并同时指向链表环入口 。
返回slow指针指向的节点。0

对应代码：

  1. class Solution {
  2. public:
  3.     ListNode *detectCycle(ListNode *head) {
  4.         ListNode*fast=head;
  5.         ListNode*slow=head;
  6.         while(fast&&fast->next){
  7.             fast=fast->next->next;
  8.             slow=slow->next;
  9.             if(slow==fast){
  10.                  fast=head;
  11.                  while(fast!=slow){
  12.                      fast=fast->next;
  13.                      slow=slow->next;
  14.                  }
  15.                  return slow;
  16.             }
  18.         }
  19.         return NULL;
  20.     }
  21. };

分割链表：

对应letecode链接：
面试题 02.04. 分割链表 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2

输入：head = [2,1], x = 2
输出：[1,2]

提示：

链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200

解题思路：

只需要遍历链表的所有节点，小于x的放到一个小的链表中，大于等于x的放到一个大的链表中，最后再把这两个链表串起来即可。

对应代码：

  1. class Solution {
  2. public:
  3.     ListNode* partition(ListNode* head, int x) {
  4.           ListNode*smallHead=new ListNode(-1);
  5.           //小链表的头
  6.           ListNode*bigHead=new ListNode(-1);
  7.          // 大链表的头
  8.           ListNode*smallTail=smallHead;
  9.           //小链表的尾
  10.           ListNode*bigTail=bigHead;
  11.           //大链表的尾
  12.           //变量链表
  13.           while(head){
  14.               if(head->val<x){
  15.                      smallTail->next=head;//链接
  16.                      smallTail=smallTail->next;
  17.               }
  18.               else{
  19.                   bigTail->next=head;
  20.                   bigTail=bigTail->next;//链接
  21.               }
  22.               head=head->next;
  23.           }
  24.           smallTail->next=bigHead->next;
  25.           bigTail->next=nullptr;//防止成环
  26.           return smallHead->next;
  28.     }
  29. };

运行结果：

回文链表：

对应letecode链接：
力扣

题目描述:

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：

输入: head = [1,2,3,3,2,1]
输出: true
示例 2：

输入: head = [1,2]
输出: false

提示：

链表 L 的长度范围为 [1, 105]
0 <= node.val <= 9

进阶：能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解题思路：基本步骤上面都已经做过了

把链表分成前后两段，当链表节点数为奇数时，前半段要比后半段多一个节点；
把链表的后半段进行反转；
判断前半段链表和反转后的链表各节点值是否相同。若前半段比后半段多一个节点，多出的节点不做判断。
判断的时候使用两个指针指向前后段的头节点，逐各对比，直至指针 p2 为空。

对应代码：

反转代码：

  1. ListNode*Reverse(ListNode*head)
  2.        {
  3.             iF(!head||!head->next)return head;
  4.             ListNode* res=Reverse(head->next);
  5.            head->next->next=head;
  6.            head->next=nullptr;
  7.            return res;
  8.        }

分割链表的代码：

  1. ListNode*GetMid(ListNode*head)
  2.        {
  3.                  ListNode*prev=nullptr;
  4.                 ListNode*slow=head;
  5.                 ListNode*fast=head;
  6.                 while(fast&&fast->next)
  7.                  {
  8.                      prev=slow;
  9.                      fast=fast->next->next;
  10.                      slow=slow->next;
  11.                  }
  12.                  prev->next=nullptr;
  13.                  return slow;
  14.        }
  1. bool isPalindrome(ListNode* head) {
  2.           if(head==nullptr||head->next==nullptr)
  3.                        return true;
  4.             ListNode*P2=GetMid(head);
  5.                 P2=Reverse(P2);
  6.                  ListNode*P1=head;
  7.                  while(P2&&P1){
  8.                      if(P1->val!=P2->val){
  9.                          return false;
  10.                      }
  11.                      P1=P1->next;
  12.                      P2=P2->next;
  13.                  }
  14.                   return true;
  15.     }
  16. };

总代码：

  1. class Solution {
  2. public:
  3.        ListNode*GetMid(ListNode*head)
  4.        {
  5.                  ListNode*prev=nullptr;
  6.                 ListNode*slow=head;
  7.                 ListNode*fast=head;
  8.                 while(fast&&fast->next)
  9.                  {
  10.                      prev=slow;
  11.                      fast=fast->next->next;
  12.                      slow=slow->next;
  13.                  }
  14.                  prev->next=nullptr;
  15.                  return slow;
  16.        }
  18.        ListNode*Reverse(ListNode*head)
  19.        {
  20.             if(!head||!head->next)return head;
  21.             ListNode* res=Reverse(head->next);
  22.            head->next->next=head;
  23.            head->next=nullptr;
  24.            return res;
  25.        }
  27.     bool isPalindrome(ListNode* head) {
  28.           if(head==nullptr||head->next==nullptr)
  29.                        return true;
  30.             ListNode*P2=GetMid(head);//将链表一分为二
  31.                 P2=Reverse(P2);//反转后半段链表
  32.                  ListNode*P1=head;
  33.                  while(P2&&P1){
  34.                      if(P1->val!=P2->val){//一一比较
  35.                          return false;
  36.                      }
  37.                      P1=P1->next;
  38.                      P2=P2->next;
  39.                  }
  40.                   return true;
  41.     }
  42. };

链表相交：

对应letecode链接：
面试题 02.07. 链表相交 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
 

进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

解题思路：双指针

我们还可以使用两个指针，最开始的时候一个指向链表A，一个指向链表B，然后他们每次都要往后移动一位，顺便查看节点是否相等。如果链表A和链表B不相交，基本上没啥可说的，我们这里假设链表A和链表B相交。那么就会有两种情况，

一种是链表A的长度和链表B的长度相等，他们每次都走一步，最终在相交点肯定会相遇。

一种是链表A的长度和链表B的长度不相等，如下图所示：

虽然他们有交点，但他们的长度不一样，所以他们完美的错开了，即使把链表都走完了也找不到相交点。

我们仔细看下上面的图，如果A指针把链表A走完了，然后再从链表B开始走到相遇点就相当于把这两个链表的所有节点都走了一遍，同理如果B指针把链表B走完了，然后再从链表A开始一直走到相遇点也相当于把这两个链表的所有节点都走完了

所以如果A指针走到链表末尾，下一步就让他从链表B开始。同理如果B指针走到链表末尾，下一步就让他从链表A开始。只要这两个链表相交最终肯定会在相交点相遇，如果不相交，最终他们都会同时走到两个链表的末尾，我们来画个图看一下：

从上面之中我们可以知道：A指针和B指针如果一直走下去，那么他们最终会在相交点相遇，最后

代码实现：

  1. class Solution {
  2. public:
  3.     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  4.                 ListNode*tempA=headA;
  5.                 ListNode*tempB=headB;
  6.                 while(tempA!=tempB){
  7.                     //如果指针tempA不为空，tempA就往后移一步。
  8.         //如果指针tempA为空，就让指针tempA指向headB（注意这里是headB不是tempB）
  9.                       tempA=(tempA==nullptr?headB:tempA->next);
  10.                       tempB=(tempB==nullptr?headA:tempB->next);
  11.                 }
  12.                 return tempA; //tempA要么是空，要么是两链表的交点
  13.     }
  14. };

其实本题还又另外一种思路就是：

统计两个链表的长度，找到两个链表长的那个，让后让长的那个先走两个链表长度的绝对值之差的长度，然后在同时遍历链表，看是不是有节点相等，如果有则返回相同时的指针，如果遍历完了还没有找到相等的就返回nullptr,各位铁子们可以下去自己试一下 

各位大佬动动你们的小手给博主点个赞！谢谢

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/qq_56999918/article/details/121480160

内容来源于网络，如有侵权，请联系作者删除！

c++c语言html5

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com