算法打卡|Day4 链表part02

Day4 链表part02

今日任务
● 24. 两两交换链表中的节点
● 19.删除链表的倒数第N个节点
● 面试题 02.07. 链表相交
● 142.环形链表II


[TOC]

Problem: 24. 两两交换链表中的节点

思路

1.迭代法就要注意画图!画图!还是画图!另外迭代的次序不要忘记,链表迭代统一从左往右迭代。用三个结点去一遍遍迭代


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)
拓展
*/

//思路:两两交换链表中的节点,拿第一个节点头节点head与第二个节点newHead(newHead = head.next) 来讲,需要将head与newHead交换位置,使newHead变成链表中的头节点,head变成第二个节点,然后head再指向已经处理好的链表,以此类推,递归调用本身,直到最后只剩下一个节点或者为空,结束返回新的头指针,也就是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 个结点

思路

首先我们要用快慢指针,快指针先走,慢指针再和快指针同步走。不过,要删除一个节点需要走到那个节点的前一个,所以我们要让快指针多走一个。比如要删除倒数第二个节点,我们就要让快指针先走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个节点,应该返回空,而不是原来的hea(head发生了改变);并且slow改变的是虚拟节点后续的链表
      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指向下一个节点
          else//p1走到结尾
              p1 = headB;//p1指向另一个链表头
          if(p2 != NULL)//p2没有走到结尾
              p2 = p2->next;//p2指向下一个节点
          else  //p2走到结尾 
              p2 = headA;//p2指向另一个链表头
      }
      return p1;
      
  }
};

Problem: 24. 两两交换链表中的节点

[TOC]

思路

1.迭代法就要注意画图!画图!还是画图!另外迭代的次序不要忘记,链表迭代统一从左往右迭代。用三个结点去一遍遍迭代


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)
拓展
*/

//思路:两两交换链表中的节点,拿第一个节点头节点head与第二个节点newHead(newHead = head.next) 来讲,需要将head与newHead交换位置,使newHead变成链表中的头节点,head变成第二个节点,然后head再指向已经处理好的链表,以此类推,递归调用本身,直到最后只剩下一个节点或者为空,结束返回新的头指针,也就是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;
  }
};

热门相关:神秘总裁小小妻   宠物小精灵之庭树   嫡嫁千金   异能特工:军火皇后   嫡嫁千金