鏈表問題（一）-LeetCode 138、382、203、143、141、142（有環鏈表入環節點，複製複雜鏈表）

• 2019 年 12 月 13 日
• 筆記

鏈表問題（一）：LeetCode #138 382 203 143 141 142

1

編程題

【LeetCode #138】複製帶隨機指針的複雜鏈表

解題思路： 如圖所示：

class Solution {  public:      Node* copyRandomList(Node* head) {          if(head == nullptr)  return nullptr;          Node* cur = head;          Node* pNext = nullptr;          // 第一步：1 -> 1' -> 2 -> 2' ...          while(cur != nullptr){              pNext = cur->next;              cur->next = new Node(cur->val);              cur->next->next = pNext;              cur = pNext;          }          // 第二步：修改random指針為cur->random->next          cur = head;          Node* copyNode = nullptr;          while(cur != nullptr){              pNext = cur->next->next;              copyNode = cur->next;              copyNode->random = ((cur->random == nullptr) ? nullptr : cur->random->next);              cur = pNext;          }          cur = head;          Node* res = cur->next;          while(cur != nullptr){              pNext = cur->next->next;              copyNode = cur->next;              cur->next = pNext;              copyNode->next = (pNext != nullptr) ? pNext->next : nullptr;              cur = pNext;          }          return res;      }  };  

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

【LeetCode #382】鏈表的隨機節點

給定一個單鏈表，隨機選擇鏈表的一個節點，並返回相應的節點值。保證每個節點被選的概率一樣。 進階: 如果鏈表十分大且長度未知，如何解決這個問題？你能否使用常數級空間複雜度實現？

示例: // 初始化一個單鏈表 [1,2,3]. ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); Solution solution = new Solution(head); // getRandom()方法應隨機返回1,2,3中的一個，保證每個元素被返回的概率相等。 solution.getRandom();

解題思路：

首先遍歷得到鏈表的長度，然後使用rand函數獲取隨機值，在找到對應節點！

class Solution {  public:      /** @param head The linked list's head.          Note that the head is guaranteed to be not null, so it contains at least one node. */      Solution(ListNode* head) {          phead = head;          while(head != nullptr){              size++;              head = head->next;          }      }        /** Returns a random node's value. */      int getRandom() {          ListNode* cur = phead;          int k = rand() % size;          for(int i = ; i < k; i++){              cur = cur->next;          }          return cur->val;      }  private:      int size = ;      ListNode* phead;  };  

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/linked-list-random-node

【LeetCode #203】移除鏈表元素

刪除鏈表中等於給定值 val 的所有節點。

示例: 輸入: 1->2->6->3->4->5->6, val = 6 輸出: 1->2->3->4->5

解題思路：

由於有可能是頭結點被刪除，因此需要使用哨兵節點dummy，在遍歷刪除中只使用一個指針pre，由於在循環中使用了pre->next->next, 因此while中的條件應該為pre->next != nullptr.

class Solution {  public:      ListNode* removeElements(ListNode* head, int val) {          ListNode* dummy = new ListNode(-1);  // pre指向dummy節點          dummy->next = head;          ListNode* pre = dummy;          while(pre->next != nullptr){              if(pre->next->val == val){                  pre->next = pre->next->next;                }else{                  pre = pre->next;              }          }          return dummy->next;      }  };  

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/remove-linked-list-elements/

【LeetCode #143】重排鏈表

給定一個單鏈表 L：L0→L1→…→Ln-1→Ln ， 將其重新排列後變為：L0→Ln→L1→Ln-1→L2→Ln-2→… 你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換。

示例 1: 給定鏈表 1->2->3->4, 重新排列為 1->4->2->3.

解題思路：

將每個節點的指針放入vector中，然後進行連接，直接原地O(1)太難了，我記不住。。。

class Solution {  public:      void reorderList(ListNode* head) {          if(head == nullptr) return;          vector<ListNode*> vec;          while(head != nullptr){              vec.push_back(head);              head = head->next;          }          int left = , right = vec.size()-1;          while(left < right){              vec[left]->next = vec[right];              vec[right--]->next = vec[++left];          }          vec[left]->next = nullptr;      }  };  

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/reorder-list

【LeetCode #141】環形鏈表

給定一個鏈表，判斷鏈表中是否有環。

為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環。

示例 1： 輸入：head = [3,2,0,-4], pos = 1 輸出：true 解釋：鏈表中有一個環，其尾部連接到第二個節點。

解題思路：

使用快慢指針，慢指針一次走一步，快指針一次走兩步，如果有環，必定相遇，否則快指針會指向nullptr。

class Solution {  public:      bool hasCycle(ListNode *head) {          if(head == nullptr ||          head->next == nullptr ||          head->next->next == nullptr) return false;   // 兩個節點以上才會有環            ListNode *slow = head, *fast = head;          while(fast != nullptr){              slow = slow->next;              fast = (fast->next != nullptr) ? fast->next->next : nullptr;              if(slow == fast) return true;          }          return false;      }  };  

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/linked-list-cycle

【LeetCode #142】環形鏈表II

給定一個鏈表，返回鏈表開始入環的第一個節點。如果鏈表無環，則返回 null。 為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環。

說明：不允許修改給定的鏈表。

示例 1： 輸入：head = [3,2,0,-4], pos = 1 輸出：tail connects to node index 1 解釋：鏈表中有一個環，其尾部連接到第二個節點。

解題思路：

仍然是快慢指針，快指針一次走兩步，慢指針一次走一步，上一題只需要判斷有環無環即可，因此只需要相遇一次就好了，但這一題需要返回入環節點，因此需要相遇兩次！在第一次相遇後，將慢指針指向頭部位置，同時快指針改為一次走一步，第二次相遇的節點即為入環節點！

class Solution {  public:      ListNode *detectCycle(ListNode *head) {          if(head == nullptr || head->next == nullptr ||          head->next->next == nullptr)  return nullptr;            ListNode *slow = head, *fast = head;          while(fast != nullptr){              slow = slow->next;              fast = (fast->next != nullptr) ? fast->next->next : nullptr;              if(slow == fast){                  break;              }          }          if(fast == nullptr)  return nullptr;          slow = head;          while(slow != fast){              slow = slow->next;              fast = fast->next;          }          return slow;      }  };  

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/linked-list-cycle-ii