博客 / 詳情

返回

鏈表-刪除、合併

鏈表

刪除鏈表中的某個節點或某一段區間

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/

leetcode個人解題總結 , c++ , 數據結構與算法
user avatar tulingxiaobian 頭像 mrbone11 頭像
2 位用戶收藏了這個故事！

發佈 評論

Some HTML is okay.