Day4 鏈表part02

今日任務
● 24. 兩兩交換鏈表中的節(jié)點
● 19.刪除鏈表的倒數第N個節(jié)點
● 面試題 02.07. 鏈表相交
● 142.環(huán)形鏈表II

Problem: 24. 兩兩交換鏈表中的節(jié)點

思路

1.迭代法就要注意畫圖！畫圖！還是畫圖！另外迭代的次序不要忘記，鏈表迭代統(tǒng)一從左往右迭代。用三個結點去一遍遍迭代

2.使用遞歸法，先交換前兩個結點，然后指向遞歸好的鏈表就行。

解題方法

迭代或遞歸文章來源地址http://www.zghlxwxcb.cn/news/detail-710354.html

Code

/**
時間復雜度：O(n)
空間復雜度：O(1)
*/
class Solution {
public:
  ListNode* swapPairs(ListNode* head) {
      auto dummy = new ListNode(0,head);
      ListNode* a = dummy;
      while (a->next != nullptr && a->next->next != nullptr){          

          ListNode* b = a->next;
          ListNode* c = a->next->next;
          a->next = c;
          b->next =c->next;
          c->next =b;
          a = b;
      }
      return dummy->next;
  }
  
};

Code

/**
時間復雜度：O(n)
空間復雜度：O(n)
拓展
*/

//思路：兩兩交換鏈表中的節(jié)點，拿第一個節(jié)點頭節(jié)點head與第二個節(jié)點newHead(newHead = head.next) 來講，需要將head與newHead交換位置，使newHead變成鏈表中的頭節(jié)點，head變成第二個節(jié)點，然后head再指向已經處理好的鏈表，以此類推，遞歸調用本身，直到最后只剩下一個節(jié)點或者為空，結束返回新的頭指針，也就是newHead
class Solution {
public:
  ListNode* swapPairs(ListNode* head) {
      //遞歸邊界條件, 有2個結點才需要交換
      if(head == nullptr || head->next == nullptr){
          return head;
      }
      ListNode* newHead =head->next;
      head->next = swapPairs(newHead->next);
      newHead->next = head;
      return newHead;
  }
};

Problem: 19. 刪除鏈表的倒數第 N 個結點

思路

首先我們要用快慢指針，快指針先走，慢指針再和快指針同步走。不過，要刪除一個節(jié)點需要走到那個節(jié)點的前一個，所以我們要讓快指針多走一個。比如要刪除倒數第二個節(jié)點，我們就要讓快指針先走3格。最后記得虛擬頭結點，因為可能涉及到真實頭結點的刪除。

解題方法

雙指針

Code

/**
時間復雜度: O(n)
空間復雜度: O(1)
*/
class Solution {
public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
      ListNode* dummyhead = new ListNode(0, head);
      ListNode* fast = dummyhead;
      ListNode* slow = dummyhead;
      n++;
      while(n-- && fast != nullptr){
          fast = fast->next;
      }

      while(fast!=nullptr){
          slow = slow->next;
          fast = fast->next;
      }

      slow->next = slow->next->next;

      //此處不能head，因為如果只有1個節(jié)點，應該返回空，而不是原來的hea（head發(fā)生了改變）；并且slow改變的是虛擬節(jié)點后續(xù)的鏈表
      return dummyhead->next;

  }
};

Problem: 面試題 02.07. 鏈表相交

思路

如果有公共結點肯定是在后面重疊，且后面部分都是共同的。
方法1：先計算出兩個鏈表的長度，可以讓比較長的先走兩個鏈表長度之差的步數，兩個再一起走。
方法2：不同部分為a， 和b，公共部分為c；a + c + b = b + c + a;讓兩個一起走，a走到頭就轉向b， b走到頭轉向a，則在公共部分相遇。

解題方法

雙指針法

復雜度

• 時間復雜度:

$O(2n)$

• 空間復雜度:

$O(1)$

Code

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
      ListNode *p1 = headA;
      ListNode *p2 = headB;

      while (p1 != p2) {
          if(p1 != NULL)//p1沒有走到結尾
              p1 = p1->next;//p1指向下一個節(jié)點
          else//p1走到結尾
              p1 = headB;//p1指向另一個鏈表頭
          if(p2 != NULL)//p2沒有走到結尾
              p2 = p2->next;//p2指向下一個節(jié)點
          else  //p2走到結尾 
              p2 = headA;//p2指向另一個鏈表頭
      }
      return p1;
      
  }
};

Problem: 24. 兩兩交換鏈表中的節(jié)點

思路

1.迭代法就要注意畫圖！畫圖！還是畫圖！另外迭代的次序不要忘記，鏈表迭代統(tǒng)一從左往右迭代。用三個結點去一遍遍迭代

2.使用遞歸法，先交換前兩個結點，然后指向遞歸好的鏈表就行。

解題方法

迭代或遞歸

Code

/**
時間復雜度：O(n)
空間復雜度：O(1)
*/
class Solution {
public:
  ListNode* swapPairs(ListNode* head) {
      auto dummy = new ListNode(0,head);
      ListNode* a = dummy;
      while (a->next != nullptr && a->next->next != nullptr){          

          ListNode* b = a->next;
          ListNode* c = a->next->next;
          a->next = c;
          b->next =c->next;
          c->next =b;
          a = b;
      }
      return dummy->next;
  }
  
};

Code

/**
時間復雜度：O(n)
空間復雜度：O(n)
拓展
*/

//思路：兩兩交換鏈表中的節(jié)點，拿第一個節(jié)點頭節(jié)點head與第二個節(jié)點newHead(newHead = head.next) 來講，需要將head與newHead交換位置，使newHead變成鏈表中的頭節(jié)點，head變成第二個節(jié)點，然后head再指向已經處理好的鏈表，以此類推，遞歸調用本身，直到最后只剩下一個節(jié)點或者為空，結束返回新的頭指針，也就是newHead
class Solution {
public:
  ListNode* swapPairs(ListNode* head) {
      //遞歸邊界條件, 有2個結點才需要交換
      if(head == nullptr || head->next == nullptr){
          return head;
      }
      ListNode* newHead =head->next;
      head->next = swapPairs(newHead->next);
      newHead->next = head;
      return newHead;
  }
};

到了這里，關于算法打卡|Day4 鏈表part02的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！