算法随想录第四天打卡|24. 两两交换链表中的节点，19.删除链表的倒数第N个节点，面试题 02.07. 链表相交 ,142.环形链表II

本文主要是介绍算法随想录第四天打卡|24. 两两交换链表中的节点，19.删除链表的倒数第N个节点，面试题 02.07. 链表相交 ,142.环形链表II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

用虚拟头结点，这样会方便很多。

本题链表操作就比较复杂了，建议大家先看视频，视频里我讲解了注意事项，为什么需要temp保存临时节点。

题目链接/文章讲解/视频讲解：代码随想录

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:if not head or not head.next:return headdummy_head=ListNode(next=head)current=dummy_headwhile current.next and current.next.next:temp=current.nexttemp1=current.next.next.nextcurrent.next=temp.nexttemp.next.next=temptemp.next=temp1current=current.next.nextreturn dummy_head.next

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummy_head=new ListNode(0);dummy_head->next=head;ListNode* current=dummy_head;while (current->next && current->next->next){ListNode* temp1=current->next;ListNode* temp2=current->next->next->next;current->next=temp1->next;temp1->next->next=temp1;temp1->next=temp2;current=current->next->next;}ListNode* temp=dummy_head->next;delete dummy_head;return temp;}
};

总结

下次要把临时节点写在循环里面，作为一个变量放在外面显得代码量很多。

19.删除链表的倒数第N个节点

双指针的操作，要注意，删除第N个节点，那么我们当前遍历的指针一定要指向第N个节点的前一个节点，建议先看视频。

题目链接/文章讲解/视频讲解：代码随想录

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:dummy_head=ListNode(next=head)slow,fast=dummy_head,dummy_headfor i in range(n):fast=fast.nextwhile fast.next:fast=fast.nextslow=slow.nextslow.next=slow.next.nextreturn dummy_head.next

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy_head=new ListNode(0);dummy_head->next=head;ListNode* fast=dummy_head;ListNode* slow=dummy_head;for (int i=0;i<n;i++)fast=fast->next;while (fast->next){fast=fast->next;slow=slow->next;}slow->next=slow->next->next;return dummy_head->next;}
};

面试题 02.07

本题没有视频讲解，大家注意数值相同，不代表指针相同。

题目链接/文章讲解：代码随想录

Python

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy_head=new ListNode(0);dummy_head->next=head;ListNode* fast=dummy_head;ListNode* slow=dummy_head;for (int i=0;i<n;i++)fast=fast->next;while (fast->next){fast=fast->next;slow=slow->next;}slow->next=slow->next->next;return dummy_head->next;}
};

C++

/*** 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* cura=headA;ListNode* curb=headB;int lena=0,lenb=0;while (cura){cura=cura->next;lena++;}while (curb){curb=curb->next;lenb++;}if (lena>lenb){for (int i=0;i<lena-lenb;i++)headA=headA->next;}else{for (int i=0;i<lenb-lena;i++)headB=headB->next;}while (headA){if (headA==headB) return headA;headA=headA->next;headB=headB->next;}return nullptr;}
};

142.环形链表II

算是链表比较有难度的题目，需要多花点时间理解确定环和找环入口，建议先看视频。

题目链接/文章讲解/视频讲解：代码随想录

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:fast,slow=head,headwhile fast and fast.next:fast=fast.next.nextslow=slow.nextif fast==slow: slow=headwhile slow!=fast:slow=slow.nextfast=fast.nextreturn fastreturn None

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast=head;ListNode* slow=head;while (fast && fast->next){fast=fast->next->next;slow=slow->next;if (fast==slow){slow=head;while (slow!=fast){slow=slow->next;fast=fast->next;}return fast;}}return nullptr;}
};