关于数据结构与算法:链表删除合并

34次阅读

共计 4727 个字符，预计需要花费 12 分钟才能阅读完成。

链表

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

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/

正文完
数据结构与算法
2022-11-19
 0
关于数据结构与算法:数据结构与算法3对数器
关于数据结构与算法:来和大家聊聊我是如何刷题的第三弹
快速幂算法-及其Python实现
关于数据结构与算法:常用排序算法之快速排序