• 链表-算法总结

    目录

    移除链表元素

    设计链表

    翻转链表

     两两交换链表中的节点

    删除链表的倒数第N个节点

    链表相交

    环形链表

    对链表中常用的，虚拟头节点，增删改查，翻转，删除倒数节点，环形链表进行了介绍

    移除链表元素

    用于单链表中删除指定元素，常用的方法包括：1虚拟节点操作，2原节点操作。

    方法：

    我们先以2原节点操作举例：

    思路在于，我们需要做两次判断，第一种为被删除元素为头节点位置，第二种为非头节点位置。

    头节点位置处理的思路是：

    如果该头节点为目标值，那么我们让头节点的下一个节点为节点，

    head = head->nex

    之和我们在返回head头节点时，其实返回的是最开始的第二个节点，那么对于第一个节点，我们还需要释放内存。所以我们定义一个中间变量 tmp 保存 head 最开始的指针，当完成节点移动后，删除 tmp也就是删除了最开始的head。

    1.         while(head != NULL && head->val == val){
    2.             //需要删除头节点
    3.             ListNode* tmp = head;
    4.             head = head->next;//头节点在第二个节点位置了
    5.             delete tmp;//释放空间最开始的头节点
    6.         }

    其他节点位置处理的思路是：

    由于当前被删除的节点必不可能为头节点，因此删除的思路是，如果该节点需要被删除，那么就让该节点的上一个节点指向被删除节点的下一个节点。同时也需要定义中间变量进行释放内存。因此整个代码如下：

    1. /**
    2.  * Definition for singly-linked list.
    3.  * struct ListNode {
    4.  *     int val;
    5.  *     ListNode *next;
    6.  *     ListNode() : val(0), next(nullptr) {}
    7.  *     ListNode(int x) : val(x), next(nullptr) {}
    8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9.  * };
    10.  */
    11. class Solution {
    12. public:
    13.     ListNode* removeElements(ListNode* head, int val) {
    14.         while(head != NULL && head->val == val){
    15.             //需要删除头节点
    16.             ListNode* tmp = head;
    17.             head = head->next;//头节点在第二个节点位置了
    18.             delete tmp;//释放空间最开始的头节点
    19.         }
    20.         //删除非头节点
    21.         ListNode* cur = head;
    22.         while(cur != NULL && cur->next != NULL){
    23.             //数组还在边界内
    24.             if(cur->next->val == val){
    25.                 ListNode* tmp = cur->next;
    26.                 cur->next = cur->next->next;//让cur指向删除的位置指向被删除位置的下一个
    27.                 delete tmp;//释放空间被删除的节点
    28.             }
    29.             else{
    30.                 cur = cur->next;
    31.             }
    32.         }
    33.         return head;
    34.     }
    35. };

    我们以1虚拟节点操作举例：

    这里的思路是：先建立一个虚拟节点，该节点指向第一个节点，那么在后续判断中就不需要再判断头节点了，直接按照删除非头节点的方式。

    1.        ListNode* dummyHead = new ListNode(0);//设置虚拟节点
    2.        dummyHead->next = head;
    3.        ListNode* cur = dummyHead;

    然后判断后续非头节点是否需要删除，因此代码如下：

    1. /**
    2.  * Definition for singly-linked list.
    3.  * struct ListNode {
    4.  *     int val;
    5.  *     ListNode *next;
    6.  *     ListNode() : val(0), next(nullptr) {}
    7.  *     ListNode(int x) : val(x), next(nullptr) {}
    8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9.  * };
    10.  */
    11. class Solution {
    12. public:
    13.     ListNode* removeElements(ListNode* head, int val) {
    14.        ListNode* dummyHead = new ListNode(0);//设置虚拟节点
    15.        dummyHead->next = head;
    16.        ListNode* cur = dummyHead;
    17.        while(cur->next != NULL){
    18.            //在有效区间内
    19.            if(cur->next->val == val){
    20.                //需要被删除
    21.                ListNode* tmp = cur->next;
    22.                cur->next = cur->next->next;
    23.                delete tmp;
    24.            }
    25.            else{
    26.                cur=cur->next;
    27.            }
    28.        }
    29.        head = dummyHead->next;//由虚拟节点指向头节点
    30.        delete dummyHead;//释放虚拟节点内存
    31.        return head;
    32.     }
    33. };

    相关题目：

    203. 移除链表元素 - 力扣（LeetCode）https://leetcode.cn/problems/remove-linked-list-elements/

    设计链表

    对单链表进行头插，尾插，任意插，任意删，获取任意节点的值。我们将分别介绍这几个部分

    方法：
    头插：

    定义一个虚拟节点指向头节点，定义一个新节点。同时，新节点指向头节点，虚拟节点指向新节点

    1.     void addAtHead(int val) {
    2.         LinkNode *newNode = new LinkNode(val);
    3.         newNode->next = _dummyHead->next;//把新节点指向头节点
    4.         _dummyHead->next = newNode;//把虚拟节点指向新节点
    5.         _size++;//节点数量增加
    6.     }

    尾插：

    定义一个指针指向虚拟节点，定义一个新节点被最后位置指向

    1.     void addAtTail(int val) {
    2.         LinkNode* newNode = new LinkNode(val);
    3.         LinkNode* cur = _dummyHead;
    4.         //这里cur不一样可以试着代值进去
    5.         while(cur->next != nullptr){
    6.             cur = cur->next;
    7.         }
    8.         cur->next = newNode;
    9.         _size++;
    10.     }

    任意插：

    1.     void addAtIndex(int index, int val) {
    2.         if(index > _size || index < 0){
    3.             return ;
    4.         }
    5.         LinkNode* newNode = new LinkNode(val);
    6.         LinkNode* cur = _dummyHead;
    7.         while(index--){
    8.             cur = cur->next;
    9.         }
    10.         newNode->next = cur->next;;
    11.         cur->next = newNode;
    12.         _size++;
    13.     }

    任意删：

    1.     void deleteAtIndex(int index) {
    2.         if(index >= _size || index < 0){
    3.             return ;
    4.         }
    5.         LinkNode* cur =_dummyHead;
    6.         while(index--){
    7.             cur = cur->next;
    8.         }
    9.         LinkNode* tmp = cur->next;
    10.         cur->next = cur->next->next;
    11.         delete tmp;
    12.         _size--;
    13.     }

    相关题目：

    707. 设计链表 - 力扣（LeetCode）https://leetcode.cn/problems/design-linked-list/

    翻转链表

    原理：

    对于单链表进行元素翻转时，我们利用双指针方法，分别指向前后节点，交换节点指向顺序实现整个链表的翻转

    方法：

    包括：1双指针法，2递归法实现，两者思路一样，需要注意的是，在翻转之后移动指针时，先移动后指针再移动前指针。

    我们现在以双指针举例：

    定义一个cur指向前节点赋值为head，定义一个后节点赋值为NULL。因为翻转后，之前的头节点需要指向NULL

    1.         ListNode* cur = head;//后节点
    2.         ListNode* pre = NULL;//前节点

    当前节点指向NULL，也就是之前的尾节点时结束循环，同时利用一个中间变量保存cur的下一个节点，因为我们需要把cur的下一个节点赋值给pre，没有中间变量将导致找不到下一个节点了。当完成一次翻转后，后节点，前节点依次前移

    1. class Solution {
    2. public:
    3.     ListNode* reverseList(ListNode* head) {
    4.         ListNode* cur = head;//后节点
    5.         ListNode* pre = NULL;//前节点
    6.         while(cur){
    7.             //当cur指向空结束
    8.             ListNode* temp = cur->next;//保留cur之前的下一个节点
    9.             cur->next = pre;//指针翻转;
    10.             //指针同时前移，先移pre，再cur
    11.             pre = cur;
    12.             cur = temp;
    13.         }
    14.         return pre;
    15.     }
    16. };

    我们现在以递归举例：

    由双指针思路一样，我们递归函数为reverse（），其中传入为reverse（head，NULL），也就是之前的（cur，pre），然后返回pre

     return reverse(head,NULL);

    当cur=NULL时结束，返回pre

    1.         if(cur == NULL){
    2.             //结束
    3.             return pre;
    4.         }

    定义中间变量和翻转节点，这里和双指针一样

    1.         ListNode* temp = cur->next;
    2.         cur->next = pre;//翻转指针

    现在前移节点，按照双指针，先移动pre，再移动cur，因此传入的reverse按照这个样子，总代码如下：

    1. class Solution {
    2. public:
    3.     ListNode* reverse(ListNode* cur,ListNode* pre){
    4.         if(cur == NULL){
    5.             //结束
    6.             return pre;
    7.         }
    8.         ListNode* temp = cur->next;
    9.         cur->next = pre;//翻转指针
    10.         //移动指针
    11.         return reverse(temp, cur);
    12.     }
    13.     ListNode* reverseList(ListNode* head) {
    14.         return reverse(head,NULL);//cur,pre的顺序传入,返回pre
    15.  
    16.     }
    17. };

    相关题目：
    206. 反转链表 - 力扣（LeetCode）https://leetcode.cn/problems/reverse-linked-list/

     两两交换链表中的节点

    创建虚拟头节点指向头节点，定义一个指针指向虚拟头节点，以及保存 1， 3节点的指针 

    1.         ListNode* dummyHead = new ListNode(0);//虚拟头节点
    2.         dummyHead->next = head;
    3.         ListNode* cur = dummyHead;
    4.             //1.保存 1，3节点
    5.             ListNode* temp1 = cur->next;
    6.             ListNode* temp2 = cur->next->next->next;

    判断链表遍历结束，一定要先判断cur->next。否则出现空指针报错

     while(cur->next != nullptr && cur->next->next != nullptr){

     //1.交换cur 和 2

     cur->next = cur->next->next;

     //2.交换1，2

      cur->next->next = temp1;

    //3.交换1，3

     temp1->next = temp2;

    //cur移动两个，总代码如下：

    1. /**
    2.  * Definition for singly-linked list.
    3.  * struct ListNode {
    4.  *     int val;
    5.  *     ListNode *next;
    6.  *     ListNode() : val(0), next(nullptr) {}
    7.  *     ListNode(int x) : val(x), next(nullptr) {}
    8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9.  * };
    10.  */
    11. class Solution {
    12. public:
    13.     ListNode* swapPairs(ListNode* head) {
    14.         ListNode* dummyHead = new ListNode(0);//虚拟头节点
    15.         dummyHead->next = head;
    16.         ListNode* cur = dummyHead;
    17.         while(cur->next != nullptr && cur->next->next != nullptr){
    18.             //1.保存 1，3节点
    19.             ListNode* temp1 = cur->next;
    20.             ListNode* temp2 = cur->next->next->next;
    21.             //1.交换cur 和 2
    22.             cur->next = cur->next->next;
    23.             //2.交换1，2
    24.             cur->next->next = temp1;
    25.             //3.交换1，3
    26.              temp1->next = temp2;
    27.             //cur移动两个
    28.             cur = cur->next->next;
    29.         }
    30.         return dummyHead->next;
    31.     }
    32. };

    相关题目：
    24. 两两交换链表中的节点 - 力扣（LeetCode）https://leetcode.cn/problems/swap-nodes-in-pairs/

    删除链表的倒数第N个节点

     方法：

    要删除链表中的倒数第n个节点，我们使用：双指针方法。

    定义一个虚拟头节点指向head，两个快慢指针指向虚拟节点

    1.         ListNode* dummyHead = new ListNode(0);
    2.         dummyHead->next = head;
    3.         ListNode* fast = dummyHead;
    4.         ListNode* slow = dummyHead;

    先让快指针移动n+1个位置，再让快慢指针一起移动，当快指针到了NULL时，此时慢指针在被删除元素的前一个位置。

    1.         while(n-- && fast != NULL){
    2.             fast = fast->next;
    3.             //先让fast移动n
    4.         }
    5.         //fast移动再+1，这样slow在被删除元素前一个
    6.          fast = fast->next;
    7.         //fast slow一起移动，直到fast到NULL
    8.         while(fast != NULL){
    9.             fast = fast->next;
    10.             slow = slow->next;
    11.         }

    现在进行元素删除，让slow的next指向被删除元素的下一个，同时释放内存，总代码如下

    1. /**
    2.  * Definition for singly-linked list.
    3.  * struct ListNode {
    4.  *     int val;
    5.  *     ListNode *next;
    6.  *     ListNode() : val(0), next(nullptr) {}
    7.  *     ListNode(int x) : val(x), next(nullptr) {}
    8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9.  * };
    10.  */
    11. class Solution {
    12. public:
    13.     ListNode* removeNthFromEnd(ListNode* head, int n) {
    14.         ListNode* dummyHead = new ListNode(0);
    15.         dummyHead->next = head;
    16.         ListNode* fast = dummyHead;
    17.         ListNode* slow = dummyHead;
    18.         while(n-- && fast != NULL){
    19.             fast = fast->next;
    20.             //先让fast移动n
    21.         }
    22.         //fast移动再+1，这样slow在被删除元素前一个
    23.          fast = fast->next;
    24.         //fast slow一起移动，直到fast到NULL
    25.         while(fast != NULL){
    26.             fast = fast->next;
    27.             slow = slow->next;
    28.         }
    29.         ListNode* temp = slow->next;
    30.         slow->next = slow->next->next;
    31.         delete temp;
    32.         return dummyHead->next;
    33.     }
    34.    
    35. };

    相关题目：
    19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）icon-default.png?t=M85Bhttps://leetcode.cn/problems/remove-nth-node-from-end-of-list/

    链表相交

    方法：
    求两个链表相交的位置，如果没有就返回空，我们利用一个巧妙办法，先让比较长的链表的头指针移动两个链表的差距长度，然后以长链表开始，遍历两个链表的节点是否一样。

    1. /**
    2.  * Definition for singly-linked list.
    3.  * struct ListNode {
    4.  *     int val;
    5.  *     ListNode *next;
    6.  *     ListNode(int x) : val(x), next(NULL) {}
    7.  * };
    8.  */
    9. class Solution {
    10. public:
    11.     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    12.         ListNode* curA = headA;
    13.         ListNode* curB = headB;
    14.         int lenA = 0, lenB = 0;
    15.         //求A，B链表长度
    16.         while(curA != NULL){
    17.             lenA++;
    18.             curA = curA->next;
    19.         }
    20.         while(curB != NULL){
    21.             lenB++;
    22.             curB = curB->next;
    23.         }
    24.         //让curA，curB回到头节点
    25.         curA = headA;
    26.         curB = headB;
    27.         //找到最长链表，设置为A
    28.         if(lenB > lenA){
    29.             swap(lenA,lenB);
    30.             swap(curA,curB);
    31.         }
    32.         //求差距长度
    33.         int gap = lenA - lenB;
    34.         while(gap--){
    35.             curA = curA->next;
    36.             //curA移动gap个长度
    37.         }
    38.         //遍历A，B是否有相同的
    39.         while(curA != NULL){
    40.             if(curA == curB){
    41.                 return curA;
    42.             }
    43.             curA = curA->next;
    44.             curB = curB->next;
    45.         }
    46.         return NULL;
    47.     }
    48. };

    相关题目：

    面试题 02.07. 链表相交 - 力扣（LeetCode）icon-default.png?t=M85Bhttps://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

    环形链表

     方法：

    利用双指针实现，题目满足当快慢指针相遇后，同时移动z个距离必定相遇。

    根据这个要求：我们做如下工作：

    让快慢指针一起移动，并且满足在边界范围内

    1.  while(fast != NULL && fast->next != NULL){
    2.             fast = fast->next->next;
    3.             slow = slow->next;
    4. }

    当移动过程中两者相遇，则让两者继续移动，两者必定会碰到

    1.  if(fast == slow){
    2.                 ListNode* index1 = head;
    3.                 ListNode* index2 = fast;
    4.                 while(index1 != index2){
    5.                     //直到两者在移动z个距离碰到
    6.                     index1 = index1->next;
    7.                     index2 = index2->next;
    8.                 }

    完整代码如下：

    1. /**
    2.  * Definition for singly-linked list.
    3.  * struct ListNode {
    4.  *     int val;
    5.  *     ListNode *next;
    6.  *     ListNode(int x) : val(x), next(NULL) {}
    7.  * };
    8.  */
    9. class Solution {
    10. public:
    11.     ListNode *detectCycle(ListNode *head) {
    12.         ListNode* fast = head;
    13.         ListNode* slow = head;
    14.         while(fast != NULL && fast->next != NULL){
    15.             fast = fast->next->next;
    16.             slow = slow->next;
    17.             //一直移动快慢指针,直到相遇
    18.             if(fast == slow){
    19.                 ListNode* index1 = head;
    20.                 ListNode* index2 = fast;
    21.                 while(index1 != index2){
    22.                     //直到两者在移动z个距离碰到
    23.                     index1 = index1->next;
    24.                     index2 = index2->next;
    25.                 }
    26.                 return index1;
    27.             }
    28.         }
    29.         return NULL;
    30.  
    31.     }
    32. };

    相关题目：

    142. 环形链表 II - 力扣（LeetCode）icon-default.png?t=M85Bhttps://leetcode.cn/problems/linked-list-cycle-ii/

  • 相关阅读:
    选择合格的数据采集公司，需注意这些
    spring service事务传播
    数据链路层协议
    线程安全,,Maven基本介绍,220822,,
    redis笔记 三 redis持久化
    饿了么官宣合作抖音后，美团的失意是什么？
    YOLOv5报错：TypeError: load() missing 1 required positional argument: ‘Loader‘
    idea插件推荐
    C++ Reference: Standard C++ Library reference: C Library: cctype: isgraph
    计算机网络实验 第四次 11月1日
  • 原文地址：https://blog.csdn.net/m0_60524373/article/details/126765932