精益求精解LeetCode(82與83)

2019 年 10 月 6 日
筆記

好久沒有刷題與更文了，今天來一場LeetCode上面簡單與中等題目多種方法刷題。

1.題目

83. 刪除排序鏈表中的重複元素

給定一個排序鏈表，刪除所有重複的元素，使得每個元素只出現一次。

示例 1:

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

輸入: 1->1->2->3->3輸出: 1->2->3

2.思想

（1）使用快慢指針

特殊情況判斷：鏈表為空或鏈表只有一個節點，直接返回。

設p=head，q=head->next，讓不斷去移動，直到q的val不等於p的val，那麼將p連接上q即可。

循環特殊情況判斷，當快指針指向為空，直接讓p指向NULL，break掉函數，返回即可。

分析：時間複雜度為O(n)，空間複雜度為O(1)。

class Solution {  public:      ListNode* deleteDuplicates(ListNode* head) {          if(head==NULL||head->next==NULL) return head;          ListNode *p=head,*q=p->next;          while(p) {              if(p->val!=q->val) {                  p->next=q;                  p=q;              }              q=q->next;              if(q==NULL){                  p->next=NULL;                  break;              }          }          return head;      }  };

（2）遞歸

遞歸終止條件：無節點或只有一個節點。

遞歸到最後，例如尾部節點為2 2，也就是當head->next指向末尾的2時候，此時需要判斷head與head->next值是否相等，如果相等，直接讓head指向尾部，依次覆蓋所有重複節點。否則，直接讓head指向尾部節點。

分析：時間複雜度為O(n)，空間複雜度為O(1)。

ListNode* deleteDuplicates(ListNode* head) {      //鏈表是否為空或者是否到末尾      if (head == NULL || head->next == NULL)          return head;      ListNode *p = deleteDuplicates(head->next);      if (head->val == head->next->val)          head = p;      else          head->next = p;      return head;  }

2.題目

82. 刪除排序鏈表中的重複元素 II

給定一個排序鏈表，刪除所有含有重複數字的節點，只保留原始鏈表中沒有重複出現的數字。

示例 1:

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

輸入: 1->1->1->2->3輸出: 2->3

3.思想

3.1方法一

這道題與上述題目很相似，於是採用上述題目思想完成。

上述思想中核心就是快慢指針，快指針q，滿指針p，每次q指向的是新元素，也就是滿足p->val!=q->val,就需要判斷當前鏈表是否值不同連續。

值不同連續判斷就是p->next==q,(兩者距離只差1)。如果滿足,說明當前p指向的元素無重複,那麼直接讓r(此指針為新返回鏈表的遍歷指針)指針指向p指向的節點(注意這裡是創建了一個p->val相同的節點)，r指針再指向下一個節點，q指針處理是不作為循環的遍歷指針,每次++。

到最後,q指針為空,分為兩種情況：

（1）值不同不連續: 例如：[1,2,2] p指向了2,q指向了NULL,此時需要將r->next指針直接指向末尾的NULL*

（2）值不同連續: 例如：[1,2,2,5] p指向了5,q指向了NULL,此時需要連接p,即r->next=p

ListNode* deleteDuplicates(ListNode* head) {      if(head==NULL || head->next==NULL) return head;        ListNode* p=head,*q=p->next;      ListNode* HEAD=new ListNode(0),*r=HEAD;        while(q) {          cout<<p->val<<" "<<q->val<<endl;            if(p->val!=q->val) {              if(p->next==q) {                  r->next=new ListNode(p->val);                  r=r->next;              }                p=q;          }          cout<<r->val<<endl;          q=q->next;      }      if(p->next!=q)          r->next=NULL;      else          r->next=new ListNode(p->val);      r=HEAD->next;      delete HEAD;      return r;  }

分析：*時間複雜度:O(n)，空間複雜度:O(n)。

那能否優化空間複雜度為O(1)呢？

我們繼續優化。

3.2方法二

上述的空間複雜度耗費在每次都要去創建新的節點，那麼我們不創建不就行了，只需要拓展一個指針，讓該指針不斷動態修改鏈表。

ListNode* deleteDuplicates(ListNode* head) {      // 無節點或者只有一個節點情況      if(head==NULL || head->next==NULL) return head;        // p跳躍指向不同節點,q遍歷所有節點,r動態修改鏈表      ListNode* p=head,*q=p->next,*r=p;      // 針對 [1 1 2] 這種情況需要先確定返回鏈表頭結點,那麼這裡創建一個頭結點,讓上述定義的r指針取動態的修改返回鏈表。      ListNode* HEAD=new ListNode(0); // 返回鏈表的頭指針        while(q) {          /**           * 值不同           */          if(p->val!=q->val) {              /**               * 值不同且連續               */              if(p->next==q) {                  /**                   * 返回鏈表是否有開始節點                   */                  if (HEAD->next == NULL) {                      r = p;                      HEAD->next = r;                  } else {                      r->next = p;                      r = p;                  }              }              // p指向新值              p=q;          }          q=q->next;  //遍歷鏈表      }      if(p->next!=q)          r->next=NULL;      else {          if(HEAD->next==NULL)              HEAD->next=p;          else              r->next=p;      }      r=HEAD->next;      delete HEAD;      return r;  }

到最後,q指針為空,分為兩種情況：

（1）值不同不連續

例如：[1,2,2] p指向了2,q指向了NULL,此時需要將r->next指針直接指向末尾的NULL

（2）值不同連續

值不同連續,且返回鏈表的沒有開始節點，也就是HEAD->next=NULL 例如：[1,1,2] p指向了2,q指向了NULL，此時需要連接p,但是Head->next為空,直接讓HEAD->next指向p即可
值不同連續,且回鏈表的有開始節。例如：[1,2,2,5] p指向了5,q指向了NULL,此時需要連接p,即r->next=p

分析：時間複雜度：O(n)，空間複雜度O(1)。

到此為止，自己實現的思路全部寫完，後面是看題解與評論上的一些思路，並對他們的程式碼做了一些優化後呈現出來的。

3.3 方法三

第82題用到了遞歸法，這道題也可以！

思想就是如果當前節點與後一節點相同，那麼遞歸後一節點，直到找到不同的節點，並讓前一節點(對應前面提到的當前節點)指向後一節點，依次遞歸下去，如果遞歸過程中當前節點與後一節點不同，直接鏈接，最後的head就是最終結果。

ListNode* deleteDuplicates2(ListNode* head) {      if(head==NULL || head->next==NULL) return head;        ListNode *p = head->next;        if(head->val == p->val) {          while (p&&head->val==p->val){              p=p->next;          }          head=deleteDuplicates2(p);      } else {          head->next=deleteDuplicates2(p);      }      return head;  }

時間複雜度O(n)，空間複雜度O(1)。

3.4 方法四

這個方法比較傳統，在題解中空間複雜度為O(n)，這裡我將其進行優化，最終的時間複雜度為O(n)，空間複雜度為O(1)。

思想是使用快慢指針，用慢指針跳過那些重複數，慢指針指的的元素就是返回鏈表中的元素。

ListNode* deleteDuplicates3(ListNode* head) {      if(head==NULL || head->next==NULL) return head;      // 1 1 2 2 3      ListNode *p=head,*q=p->next,*pre=head;      // 確定返回節點的頭在哪裡！      bool isonce=true;      while(p) {          if(q&&p->val==q->val) {              int tmp = p->val;              while(p&&p->val==tmp)                  p=p->next;              if(p) q=p->next;          } else {              // 1 2 3   1 1 2 3              if (isonce) {                  head = p;                  isonce = false;                  pre = head;              } else{                  pre->next = p;                  pre = p;              }              p=q;              if(q)                  q=q->next;          }      }      if(isonce) {          head=NULL;          isonce=false;      } else {          pre->next=p;      }        return head;  }

今日刷題完畢，好久沒有刷題了，累了，休息，閃了，歡迎大家轉發，收藏，點贊！