算法打卡|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;
}
};