關于【連結清單】的解題規律

連結清單

作為一個基本到不行的資料結構，連結清單可以說基本上都是擔當着服務的角色。但是連結清單本身也有非常多有趣的性質和算法的。單向連結清單的一大特點是無法知道長度和上一個結點，隻能知道目前結點和下一個結點，是以我們經常利用快慢指針的方法來線上性時間内擷取特定位置的元素。

另外在做題過程中，為了避免單獨給頭節點初始化，或删除結點時分類讨論，常常單獨new一個頭結點。

對了，順便說一下，删除結點時最好釋放一下記憶體，malloc和free配套，new和delete配套。free和delete都隻把指針所指向的記憶體釋放掉，并沒有把指針本身幹掉，故執行free或delete後都需要把指向清理記憶體的指針置為空，即p=NULL，否則指針指向的記憶體空間雖然釋放了，但是指針p的值還是記錄的那塊位址，該位址對應的記憶體是垃圾，p就成了“野指針”。

練手題：206 21(合并兩個結點) 23（21plus） 24 160 328

• 206翻轉連結清單：非常經典，三個指針共同搞定（其實可以兩個指針）。不贅述。

  class Solution {
  public:
      ListNode* reverseList(ListNode* head) {
          if(!head)   return nullptr;
          ListNode* p=head;
          ListNode* r=nullptr;
          ListNode* q;
          while(p!=nullptr){
              q=p;
              p=p->next;
              q->next=r;
              r=q;
          }
          return r;
      }
  };
             

  遞歸解法：相當于執行一次将頭節點接在某個節點前的行為，始終是頭插入，是以傳回正确

  ListNode* reverseList(ListNode* head, ListNode* prev=nullptr) {
  	if (!head) 
  		return prev;
  	ListNode* next = head->next;
  	head->next = prev;
  	return reverseList(next, head);
  }
             

• 23合并k個有序連結清單

  本題解法很多，比如類似于歸并排序進行兩兩合并。在這裡考慮把所有的連結清單存儲在一個優先隊列（小頂堆）中，每次提取所有連結清單頭部節點值最小的那個節點，直到所有連結清單都被提取完為止。注意要自己定義比較函數

  class Solution {
  public:
  //考慮建構一個優先隊列，将所有非null的節點全部放入
      struct Comp {
          bool operator() (ListNode* l1, ListNode* l2){ //注意比較函數的寫法
              return l1->val > l2->val;
          }
      };
      ListNode* mergeKLists(vector<ListNode*>& lists) {
          if(lists.empty())    return nullptr;
          priority_queue<ListNode*,vector<ListNode*>,Comp> small_heap;  
  
          ListNode* p=new ListNode();
          ListNode* q=p;
          
          //先将所有的頭元素全部入堆
          for(auto& l:lists){
              if(l)   small_heap.push(l);
          }
          //開始選擇    
          while(!small_heap.empty()){
              ListNode* r=small_heap.top();
              small_heap.pop();
              if(r->next) small_heap.push(r->next);
              p->next=r;
              p=p->next;
          }
          q=q->next;
          return q;
      }
  };
             

• 160：求兩個連結清單的相交結點

  這裡介紹一種比較巧妙的解法。假設連結清單 A 的頭節點到相交點的距離是 a，連結清單 B 的頭節點到相交點的距離是 b，相交點到連結清單終點的距離為 c。我們使用兩個指針，分别指向兩個連結清單的頭節點，并以相同的速度前進，若到達連結清單結尾，則移動到另一條連結清單的頭節點繼續前進。按照這種前進方法，兩個指針會在 a + b + c 次前進後同時到達相交節點。

  相當于把兩個連結清單進行拼接和補齊工作，最後使得相交結點位于兩個新連結清單的同一個位置。畫圖很好了解。

  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  	ListNode *l1 = headA, *l2 = headB;
  	while (l1 != l2) {
  		l1 = l1? l1->next: headB;
  		l2 = l2? l2->next: headA;
  	}
  	return l1;
  }
             

快慢指針

其實就是一快一慢兩個指針在同一個周遊循環中前進。慢指針的步長一般是1，快指針一般是2（可以根據不同題目略作修改），成功獲得連結清單中點（或第k個結點）。很好地改進了連結清單隻往後看不往前看的弊端。

ListNode *slow = head, *fast = head;
while (fast->next && fast->next->next) {
	slow = slow->next;
	fast = fast->next->next;
}
           

練手題：234（回文） 19 148

• 19：尋找倒數第k個結點

  先來講講快慢指針法。我們可以使用兩個指針first 和second 同時對連結清單進行周遊，并且first 比 second 超前 n個節點。當first 周遊到連結清單的末尾時econd 就恰好處于倒數第 n 個節點。

  另外這道題注意，設定一個頭結點可以大大簡化。

  class Solution {
  public:
      ListNode* removeNthFromEnd(ListNode* head, int n) {
          ListNode* dummy = new ListNode(0, head);
          ListNode* first = head;
          ListNode* second = dummy;
          for (int i = 0; i < n; ++i) {
              first = first->next;
          }
          while (first) {
              first = first->next;
              second = second->next;
          }
          second->next = second->next->next;
          ListNode* ans = dummy->next;
          delete dummy;
          return ans;
      }
  };
             

  還可以用隊列（或棧）來執行固定視窗滑動法。固定隊列/棧中的元素，隊列進入一個出去一個，棧最後統一彈出n個元素即可。隊列的實作方法如下：

  class Solution {
  public:
  //想法：用隊列存儲一個區間的數，進一個出一個，隊列長度為n+1，這裡多增加一個頭節點
      ListNode* removeNthFromEnd(ListNode* head, int n) {
          ListNode* myhead=new ListNode();
          myhead->next=head;
  
          queue<ListNode*> q;
          q.push(myhead);//頭節點先入隊列
          for(int i=0;i<n;i++){//資料保證了正确性
              q.push(head);
              head=head->next;
          }
          while(head){
              q.push(head);
              q.pop();
              head=head->next;
          }
          ListNode* p=q.front();
          p->next=p->next->next;
          return myhead->next;
      }
  };
             

• 148：對連結清單進行排序

  利用快慢指針找到連結清單中點後，然後對連結清單進行歸并排序。注意歸并排序的細節（用遞歸實作）

  class Solution {
  public:
  //兩個連結清單連接配接
      ListNode* merge(ListNode* list1,ListNode* list2){
          if(!list1)  return list2;
          if(!list2)  return list1;
  
          //初始化第一個節點
          ListNode* list=new ListNode();
          ListNode* result=list;
  
          while(list1 && list2){
              if(list1->val <= list2->val){
                  list->next=list1;
                  list1=list1->next;
              }
              else{
                  list->next=list2;
                  list2=list2->next;
              }
              list=list->next;
          }
          if(list1)
              list->next=list1;
          else
              list->next=list2;
          
          result=result->next;
          return result;
      }
  
      ListNode* sortList(ListNode* head) {
          //第一步，找到中點
          if(!head || !head->next)    return head;
          ListNode* slow=head;
          ListNode* fast=head;
          while(fast->next && fast->next->next){
              slow=slow->next;
              fast=fast->next->next;                   
          }
          fast=sortList(slow->next);//對後一個進行排序
          slow->next=nullptr;//注意要置空
          slow=sortList(head);
          return merge(slow,fast);
      }
  };