链表-删除、合并

发布于:2023-03-12 ⋅ 阅读:(152) ⋅ 点赞:(0)

链表

删除链表中的某个节点或某一段区间

leetcode.203

  • 链接https://leetcode.cn/problems/...
  • 解题方法:链表中删除一个节点的常规方法就是找到这个节点的前驱节点,将前驱节点的next指针指向当前节点的后继节点
  • leetcode解题代码

    /**
     * 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) {
          auto dummy = new ListNode(-1);
          dummy->next = head;
    
          for (auto p = dummy; p; p = p->next){
              auto q = p->next;
              while (q && q->val == val) q = q->next;
              p->next = q;
          }
          return dummy->next;
      }
    };

leetcode.19

  • 链接https://leetcode.cn/problems/...
  • 解题方法:与上一题类似,需要先求出链表总长度,再找到当前节点的前驱节点
    注意:当前节点的前驱节点为倒数第n+1个点,即为正数第len-n个点
    需要移动len-n-1次移动到前驱节点
  • leetcode解题代码

    /**
     * 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* removeNthFromEnd(ListNode* head, int n) {
          auto dummy = new ListNode(-1);
          dummy->next = head;
    
          int len = 0;
          for (auto p = dummy; p; p = p->next) len ++;
    
          auto p = dummy;
          for (int i = 0; i < len - n - 1; i ++) p = p->next;
          p->next = p->next->next;
          return dummy->next; 
      }
    };

leetcode.237

  • 链接https://leetcode.cn/problems/...
  • 解题方法:本题不是常规意义上的删除节点,无法像上一道题一样找到当前节点的前驱节点
    本题的方法比较取巧,即先把后继节点的值赋值给当前节点,然后再删除后继节点
  • leetcode解题代码

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
      void deleteNode(ListNode* node) {
          node->val = node->next->val;
          node->next = node->next->next;
      }
    };

leetcode.2095

  • 链接https://leetcode.cn/problems/...
  • 解题方法:快慢指针
    快指针每次向前移动两位,慢指针每次向前移动一位
    当快指针走到链表结尾,满指针刚好指向链表中间
    通过虚拟头节点让快慢指针都回退一位,满指针则刚好指向中间节点的前驱节点
  • leetcode解题代码

    /**
     * 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* deleteMiddle(ListNode* head) {
          auto dummy = new ListNode(-1);
          dummy->next = head;
          auto fast = dummy, slow = dummy;
          while (fast && fast->next && fast->next->next){
              fast = fast->next->next;
              slow = slow->next;
          }
          slow->next = slow->next->next;
          return dummy->next;
      }
    };

leetcode.83

  • 链接https://leetcode.cn/problems/...
  • 解题方法:双指针
    cur指针指向无重复元素链表的最后一个节点
    p指针遍历链表,如果p指针元素和cur指针元素不相等则将cur指针指向p,并更新cur指针
    最后cur指针是无重复元素链表的最后一个节点,记得将其指向空
  • leetcode解题代码

    /**
     * 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* deleteDuplicates(ListNode* head) {
          if (!head) return head;
          auto cur = head;
          for (auto p = head->next; p; p = p->next)
              if (p->val != cur->val)
                  cur = cur->next = p;
          cur->next = nullptr;
          return head;
      }
    };

leetcode.82

  • 链接https://leetcode.cn/problems/...
  • 解题方法:双指针
    p指针维护新链表的最后一位,q指针遍历去找无重复元素的区间
    如果区间长度=1则说明没有重复元素,保留
    如果区间长度>1则说明有重复元素,删除整个区间
  • leetcode解题代码

    /**
     * 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* deleteDuplicates(ListNode* head) {
          auto dummy = new ListNode(-1);
          dummy->next = head;
          auto p = dummy;
          while (p->next){
              auto q = p->next;
              while (q && q->val == p->next->val) q = q->next;
              if (q == p->next->next) p = p->next;
              else p->next = q;
          }
          return dummy->next;
      }
    };

合并两个有序链表

leetcode.21

  • 链接https://leetcode.cn/problems/...
  • 解题方法:归并排序
    维护一个当前节点指针
    如果list1的值小于list2,指针指向list1并更新当前节点指针和list1的指针
    如果list2的值小于list1,指针指向list2并更新当前节点指针和list2的指针
    如果两个链表长度不同,当一个链表遍历完成,另一个链表没有遍历完成,当前节点指针指向没有遍历完成的链表
  • leetcode解题代码

    /**
     * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
          auto dummy = new ListNode(-1);
          auto cur = dummy;
          while (list1 && list2){
              if (list1->val < list2->val){
                  cur = cur->next = list1;
                  list1 = list1->next;
              }
              else{
                  cur = cur->next = list2;
                  list2 = list2->next;
              }
          }
          if (list1) cur->next = list1;
          if (list2) cur->next = list2;
          return dummy->next;
      }
    };

leetcode.23

  • 链接https://leetcode.cn/problems/...
  • 解题方法:归并排序与上一题类似
    如何从k个链表中找到最小的值呢?维护一个堆
    在c++中维护一个堆用priority_queue,默认是大根堆,所以还需要重载一下比较函数
  • leetcode解题代码

    /**
     * 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:
      struct Cmp{
          bool operator() (ListNode* a, ListNode* b){
              return a->val > b->val;
          }
      };
    
      ListNode* mergeKLists(vector<ListNode*>& lists) {
          priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
          auto dummy = new ListNode(-1);
          auto cur = dummy;
          for (auto c: lists) 
              if (c) heap.push(c);
    
          while (heap.size()){
              auto t = heap.top();
              heap.pop();
    
              cur = cur->next = t;
              if (t->next) heap.push(t->next);
          }
          return dummy->next;
      }
    };

    解题参考:https://www.acwing.com/

本文含有隐藏内容,请 开通VIP 后查看