算法打卡|Day4 链表part02-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法打卡|Day4 链表part02。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Day4 链表part02

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

- Day4 链表part02
Problem: 24. 两两交换链表中的节点
- 思路
- 解题方法
- Code
- Code
Problem: 19. 删除链表的倒数第 N 个结点
- 思路
- 解题方法
- Code
Problem: 面试题 02.07. 链表相交
- 思路
- 解题方法
- 复杂度
- Code
Problem: 24. 两两交换链表中的节点
- 思路
- 解题方法
- Code
- Code

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

思路

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

2.使用递归法，先交换前两个结点，然后指向递归好的链表就行。

解题方法

迭代或递归文章来源地址https://www.toymoban.com/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)
拓展
*/

//思路：两两交换链表中的节点，拿第一个节点头节点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. 两两交换链表中的节点

- Day4 链表part02
Problem: 24. 两两交换链表中的节点
- 思路
- 解题方法
- Code
- Code
Problem: 19. 删除链表的倒数第 N 个结点
- 思路
- 解题方法
- Code
Problem: 面试题 02.07. 链表相交
- 思路
- 解题方法
- 复杂度
- Code
Problem: 24. 两两交换链表中的节点
- 思路
- 解题方法
- Code
- Code

思路

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;
  }
};

到了这里，关于算法打卡|Day4 链表part02的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！