鏈表問題（二）-LeetCode 147、876、234、817、92（鏈表的中點，快慢指針）

• 2019 年 12 月 13 日
• 筆記

1

編程題

【LeetCode #147】對鏈表進行插入排序

對鏈表進行插入排序。

示例 1： 輸入: 4->2->1->3 輸出: 1->2->3->4

解題思路：

首先判斷兩個相鄰節點的大小，如果head->val > head->next->val，則需要將head->next->val插入到從dummy節點開始遍歷第一個大於head->next->val節點的前面！好好理解這句話！在進行插入的時候，首先使用cur指針標記head->next節點，並改變head->next的指向。從而將待插入節點分離！接著就是普通的插入操作了！

/**   * Definition for singly-linked list.   * struct ListNode {   *     int val;   *     ListNode *next;   *     ListNode(int x) : val(x), next(NULL) {}   * };   */  class Solution {  public:      ListNode* insertionSortList(ListNode* head) {          if(head == nullptr || head->next == nullptr) return head;          ListNode* dummy = new ListNode(), *pre = nullptr;          dummy->next = head;          while(head->next != nullptr){              if(head->val <= head->next->val){  // 無需進行插入操作                  head = head->next;                  continue;              }              pre = dummy;              while(pre->next->val < head->next->val){                  pre = pre->next;              }              ListNode* cur = head->next;              head->next = cur->next;              cur->next = pre->next;              pre->next = cur;          }          return dummy->next;      }  };  

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

【LeetCode #876】鏈表的中間結點

給定一個帶有頭結點 head 的非空單鏈表，返回鏈表的中間結點。 如果有兩個中間結點，則返回第二個中間結點。

示例 1： 輸入：[1,2,3,4,5] 輸出：此列表中的結點 3 (序列化形式：[3,4,5]) 返回的結點值為 3 。(測評系統對該結點序列化表述是 [3,4,5])。 注意，我們返回了一個 ListNode 類型的對象 ans，這樣： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

解題思路：快慢指針，注意與下一題中的迴文鏈表的中間結點進行區別！

/**   * Definition for singly-linked list.   * struct ListNode {   *     int val;   *     ListNode *next;   *     ListNode(int x) : val(x), next(NULL) {}   * };   */  class Solution {  public:      ListNode* middleNode(ListNode* head) {          if(head == nullptr || head->next == nullptr) return head;          ListNode* slow = head, *fast = head;          while(fast != nullptr && fast->next != nullptr){              slow = slow->next;              fast = fast->next->next;          }          return slow;      }  };  

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

【LeetCode #234】迴文鏈表

請判斷一個鏈表是否為迴文鏈表。

示例 1: 輸入: 1->2 輸出: false

解題思路：

找到中點（奇數時不是真正的中點，注意與上題區別），然後反轉後面的鏈表，再進行節點值得比較即可！

/**   * Definition for singly-linked list.   * struct ListNode {   *     int val;   *     ListNode *next;   *     ListNode(int x) : val(x), next(NULL) {}   * };   */  class Solution {  public:      bool isPalindrome(ListNode* head) {          ListNode* slow = head, *fast = head, *pre = nullptr;          while(fast != nullptr){              slow = slow->next;              fast = fast->next ? fast->next->next : nullptr;          }   // 這裡的中點偶數時為第二個節點，奇數時為中點的下一個節點！          while(slow != nullptr){              ListNode* next = slow->next;              slow->next = pre;              pre = slow;              slow = next;          }          while(pre && head){              if(pre->val != head->val){                  return false;              }              pre = pre->next;              head = head->next;          }          return true;      }  };  

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

【LeetCode #817】鏈表組件

給定一個鏈表（鏈表結點包含一個整型值）的頭結點 head。 同時給定列表 G，該列表是上述鏈表中整型值的一個子集。 返回列表 G 中組件的個數，這裡對組件的定義為：鏈表中一段最長連續結點的值（該值必須在列表 G 中）構成的集合。

示例 1： 輸入: head: 0->1->2->3 G = [0, 1, 3] 輸出: 2 解釋: 鏈表中,0 和 1 是相連接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一個組件，同理 [3] 也是一個組件，故返回 2。

解題思路：

一開始題目沒有看太懂，可能語文不太好！他的意思就是，如果連續相鄰的鏈表節點值都在G這個數組中，那麼這為一個組件，如果不在，則忽略！最終答案是G中有多少個組件。 比如0->1->3->2, 而G = [1,3,0] 則答案為 1。 我們查詢可以在set中進行，設置布爾變數flag的作用是：用true標記這是一個組件，而false表示組件斷開了，此時res++, 但有可能我們遍歷的節點一直都不在G中。因此res++需要一個條件限制，即flag = true.

/**   * Definition for singly-linked list.   * struct ListNode {   *     int val;   *     ListNode *next;   *     ListNode(int x) : val(x), next(NULL) {}   * };   */  class Solution {  public:      int numComponents(ListNode* head, vector<int>& G) {          set<int> s(G.begin(), G.end());          int res = ;          bool flag = false;   // 找到標記為true          while(head != nullptr){              auto it = s.find(head->val);              if(it != s.end()){   // 找到了                  flag = true;              }else{               // 沒找到，前面的作為一個組件                  if(flag){ res++; }                  flag = false;              }              head = head->next;          }          if(flag) res++;          return res;      }  };  

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

【LeetCode #92】反轉鏈表 II

反轉從位置 m 到 n 的鏈表。請使用一趟掃描完成反轉。

說明: 1 ≤ m ≤ n ≤ 鏈表長度。

示例: 輸入: 1->2->3->4->5->NULL, m = 2, n = 4 輸出: 1->4->3->2->5->NULL

/**   * Definition for singly-linked list.   * struct ListNode {   *     int val;   *     ListNode *next;   *     ListNode(int x) : val(x), next(NULL) {}   * };   */  class Solution {  public:      ListNode* reverseBetween(ListNode* head, int m, int n) {          ListNode* dummy = new ListNode();          dummy->next = head;          ListNode* pre = dummy;          for(int i = ; i < m; i++){              pre = pre->next;          }          head = pre->next;          for(int i = m; i < n; i++){              ListNode* tmp = head->next;              head->next = tmp->next;              tmp->next = pre->next;              pre->next = tmp;          }          return dummy->next;      }  };  

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