devbox
运维做开发
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

链表篇总结_如何删除头结点

作者：运维做开发 | 2024-08-08 02:03:34

赞

踩

如何删除头结点

移除链表元素：

        给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

思路：

        这里以链表 1 4 2 4 来举例，移除元素4。

         那么因为单链表的特殊性，只能指向下一个节点，刚刚删除的是链表的中第二个，和第四个节点，那么如果删除的是头结点又该怎么办呢？

这里就涉及如下链表操作的两种方式：

  • 直接使用原来的链表来进行删除操作。
  • 设置一个虚拟头结点在进行删除操作。

来看第一种操作：直接使用原来的链表来进行移除。

        移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。

        所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。

        这样移除了一个头结点，是不是发现，在单链表中移除头结点 和 移除其他节点的操作方式是不一样，其实在写代码的时候也会发现，需要单独写一段逻辑来处理移除头结点的情况。

        那么可不可以 以一种统一的逻辑来移除 链表的节点呢。

        其实可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。

来看看如何设置一个虚拟头。依然还是在这个链表中，移除元素1。

        这里来给链表添加一个虚拟头结点为新的头结点，此时要移除这个旧头结点元素1。

        这样是不是就可以使用和移除链表其他节点的方式统一了呢？

        来看一下，如何移除元素1 呢，还是熟悉的方式，然后从内存中删除元素1。

        最后呢在题目中，return 头结点的时候，别忘了 return dummyNode->next;， 这才是新的头结点

代码：（第一个为原来链表操作，第二个为虚拟头节点操作）

  1. class Solution {
  2. public:
  3.     ListNode* removeElements(ListNode* head, int val) {
  4.         // 删除头结点
  5.         while (head != NULL && head->val == val) { // 注意这里不是if
  6.             ListNode* tmp = head;
  7.             head = head->next;
  8.             delete tmp;
  9.         }
  10.  
  11.         // 删除非头结点
  12.         ListNode* cur = head;
  13.         while (cur != NULL && cur->next!= NULL) {
  14.             if (cur->next->val == val) {
  15.                 ListNode* tmp = cur->next;
  16.                 cur->next = cur->next->next;
  17.                 delete tmp;
  18.             } else {
  19.                 cur = cur->next;
  20.             }
  21.         }
  22.         return head;
  23.     }
  24. };
  1. class Solution {
  2. public:
  3.     ListNode* removeElements(ListNode* head, int val) {
  4.         ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
  5.         dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
  6.         ListNode* cur = dummyHead;
  7.         while (cur->next != NULL) {
  8.             if(cur->next->val == val) {
  9.                 ListNode* tmp = cur->next;
  10.                 cur->next = cur->next->next;
  11.                 delete tmp;
  12.             } else {
  13.                 cur = cur->next;
  14.             }
  15.         }
  16.         head = dummyHead->next;
  17.         delete dummyHead;
  18.         return head;
  19.     }
  20. };

后面的几个题我就不写思路了，要想看思路的话，可以看我的力扣刷题栏

设计链表：

                你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

        如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/design-linked-list

代码：

  1. class MyLinkedList {
  2. public:
  3.     // 定义链表节点结构体
  4.     struct LinkedNode {
  5.         int val;
  6.         LinkedNode* next;
  7.         LinkedNode(int val):val(val), next(nullptr){}
  8.     };
  9.  
  10.     // 初始化链表
  11.     MyLinkedList() {
  12.         _dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
  13.         _size = 0;
  14.     }
  15.  
  16.     // 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
  17.     int get(int index) {
  18.         if (index > (_size - 1) || index < 0) {
  19.             return -1;
  20.         }
  21.         LinkedNode* cur = _dummyHead->next;
  22.         while(index--){ // 如果--index 就会陷入死循环
  23.             cur = cur->next;
  24.         }
  25.         return cur->val;
  26.     }
  27.  
  28.     // 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
  29.     void addAtHead(int val) {
  30.         LinkedNode* newNode = new LinkedNode(val);
  31.         newNode->next = _dummyHead->next;
  32.         _dummyHead->next = newNode;
  33.         _size++;
  34.     }
  35.  
  36.     // 在链表最后面添加一个节点
  37.     void addAtTail(int val) {
  38.         LinkedNode* newNode = new LinkedNode(val);
  39.         LinkedNode* cur = _dummyHead;
  40.         while(cur->next != nullptr){
  41.             cur = cur->next;
  42.         }
  43.         cur->next = newNode;
  44.         _size++;
  45.     }
  46.  
  47.     // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
  48.     // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
  49.     // 如果index大于链表的长度，则返回空
  50.     // 如果index小于0，则在头部插入节点
  51.     void addAtIndex(int index, int val) {
  52.  
  53.         if(index > _size) return;
  54.         if(index < 0) index = 0;        
  55.         LinkedNode* newNode = new LinkedNode(val);
  56.         LinkedNode* cur = _dummyHead;
  57.         while(index--) {
  58.             cur = cur->next;
  59.         }
  60.         newNode->next = cur->next;
  61.         cur->next = newNode;
  62.         _size++;
  63.     }
  64.  
  65.     // 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
  66.     void deleteAtIndex(int index) {
  67.         if (index >= _size || index < 0) {
  68.             return;
  69.         }
  70.         LinkedNode* cur = _dummyHead;
  71.         while(index--) {
  72.             cur = cur ->next;
  73.         }
  74.         LinkedNode* tmp = cur->next;
  75.         cur->next = cur->next->next;
  76.         delete tmp;
  77.         _size--;
  78.     }
  79.  
  80.     // 打印链表
  81.     void printLinkedList() {
  82.         LinkedNode* cur = _dummyHead;
  83.         while (cur->next != nullptr) {
  84.             cout << cur->next->val << " ";
  85.             cur = cur->next;
  86.         }
  87.         cout << endl;
  88.     }
  89. private:
  90.     int _size;
  91.     LinkedNode* _dummyHead;
  92.  
  93. };

反转链表：

①双指针法代码：

  1. class Solution {
  2. public:
  3.     ListNode* reverseList(ListNode* head) {
  4.         ListNode* temp; // 保存cur的下一个节点
  5.         ListNode* cur = head;
  6.         ListNode* pre = NULL;
  7.         while(cur) {
  8.             temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next
  9.             cur->next = pre; // 翻转操作
  10.             // 更新pre 和 cur指针
  11.             pre = cur;
  12.             cur = temp;
  13.         }
  14.         return pre;
  15.     }
  16. };

②递归法代码

  1. class Solution {
  2. public:
  3.     ListNode* reverse(ListNode* pre,ListNode* cur){
  4.         if(cur == NULL) return pre;
  5.         ListNode* temp = cur->next;
  6.         cur->next = pre;
  7.         // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
  8.         // pre = cur;
  9.         // cur = temp;
  10.         return reverse(cur,temp);
  11.     }
  12.     ListNode* reverseList(ListNode* head) {
  13.         // 和双指针法初始化是一样的逻辑
  14.         // ListNode* cur = head;
  15.         // ListNode* pre = NULL;
  16.         return reverse(NULL, head);
  17.     }
  18.  
  19. };

两两交换链表中的节点：

        给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

代码：

  1. class Solution {
  2. public:
  3.     ListNode* swapPairs(ListNode* head) {
  4.         ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
  5.         dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
  6.         ListNode* cur = dummyHead;
  7.         while(cur->next != nullptr && cur->next->next != nullptr) {
  8.             ListNode* tmp = cur->next; // 记录临时节点
  9.             ListNode* tmp1 = cur->next->next->next; // 记录临时节点
  10.  
  11.             cur->next = cur->next->next;    // 步骤一
  12.             cur->next->next = tmp;          // 步骤二
  13.             cur->next->next->next = tmp1;   // 步骤三
  14.  
  15.             cur = cur->next->next; // cur移动两位，准备下一轮交换
  16.         }
  17.         return dummyHead->next;
  18.     }
  19. };

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

        给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

 代码：

  1. class Solution {
  2. public:
  3.     ListNode* removeNthFromEnd(ListNode* head, int n) {
  4.         ListNode* dummyHead = new ListNode(0);
  5.         dummyHead->next = head;
  6.         ListNode* slow = dummyHead;
  7.         ListNode* fast = dummyHead;
  8.         while(n-- && fast != NULL) {
  9.             fast = fast->next;
  10.         }
  11.         fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
  12.         while (fast != NULL) {
  13.             fast = fast->next;
  14.             slow = slow->next;
  15.         }
  16.         slow->next = slow->next->next; 
  17.         
  18.         // ListNode *tmp = slow->next;  C++释放内存的逻辑
  19.         // slow->next = tmp->next;
  20.         // delete nth;
  21.         
  22.         return dummyHead->next;
  23.     }
  24. };

链表相交：

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

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

 

 

 

代码：

  1. class Solution {
  2. public:
  3.     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  4.         ListNode* curA = headA;
  5.         ListNode* curB = headB;
  6.         int lenA = 0, lenB = 0;
  7.         while (curA != NULL) { // 求链表A的长度
  8.             lenA++;
  9.             curA = curA->next;
  10.         }
  11.         while (curB != NULL) { // 求链表B的长度
  12.             lenB++;
  13.             curB = curB->next;
  14.         }
  15.         curA = headA;
  16.         curB = headB;
  17.         // 让curA为最长链表的头，lenA为其长度
  18.         if (lenB > lenA) {
  19.             swap (lenA, lenB);
  20.             swap (curA, curB);
  21.         }
  22.         // 求长度差
  23.         int gap = lenA - lenB;
  24.         // 让curA和curB在同一起点上（末尾位置对齐）
  25.         while (gap--) {
  26.             curA = curA->next;
  27.         }
  28.         // 遍历curA 和 curB，遇到相同则直接返回
  29.         while (curA != NULL) {
  30.             if (curA == curB) {
  31.                 return curA;
  32.             }
  33.             curA = curA->next;
  34.             curB = curB->next;
  35.         }
  36.         return NULL;
  37.     }
  38. };

环形链表II：

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

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

不允许修改 链表。

 

 

代码：

  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.             slow = slow->next;
  16.             fast = fast->next->next;
  17.             // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
  18.             if (slow == fast) {
  19.                 ListNode* index1 = fast;
  20.                 ListNode* index2 = head;
  21.                 while (index1 != index2) {
  22.                     index1 = index1->next;
  23.                     index2 = index2->next;
  24.                 }
  25.                 return index2; // 返回环的入口
  26.             }
  27.         }
  28.         return NULL;
  29.     }
  30. };
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/运维做开发/article/detail/945553
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号