代码随想录算法训练营第四天|24. 两两交换链表中的节点+19.删除链表的倒数第N个节点+160. 相交链表+142.环形链表II

非原创，搬运记录解题方法学习思路，一同进步

备忘

完成三题并搞懂思路，将方法融汇贯通完成相关题目（0/1）

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

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

思路

设置哨兵节点node0，方便交换第一个节点node1和第二个节点node2。
已知节点为node0和node1
node2和node3都是基于node1，所以首先将node0指向node2，再将node2指向node1最后将node1指向node3，至此前两个节点完成交换。
当前节点顺序更新node进行下一轮转换：

代码

# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defswapPairs(self,head:Optional[ListNode])->Optional[ListNode]:node0=dummy=ListNode(next=head)node1=headwhilenode1andnode1.next:node2=node1.nextnode3=node2.nextnode0.next=node2 node2.next=node1 node1.next=node3 node0=node1 node1=node3returndummy.next

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

思路

双指针，滑动窗口。因为多加了一个哨兵节点，所以右边界走到n时，左边界开始走直到右边界走到链表最后，此时左边界为待删除节点的前一个位置。

代码

# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defremoveNthFromEnd(self,head:Optional[ListNode],n:int)->Optional[ListNode]:left=right=dummy=ListNode(next=head)forxinrange(n):right=right.nextwhileright.next:left=left.nextright=right.nextleft.next=left.next.nextreturndummy.next

160. 相交链表

思路

走完你的走你的，一定会在共同点遇到
记住就行

代码

# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution:defgetIntersectionNode(self,headA:ListNode,headB:ListNode)->Optional[ListNode]:p,q=headA,headBwhilepisnotq:p=p.nextifpelseheadB q=q.nextifqelseheadAreturnp

142.环形链表II

思路

双指针，利用快慢找到相遇点，给我一种做奥数的感觉。记住这里判断快慢指针要用is 和 is not不是判断值而是内存地址！

代码

# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution:defdetectCycle(self,head:Optional[ListNode])->Optional[ListNode]:slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextiffastisslow:whileslowisnothead:slow=slow.nexthead=head.nextreturnslowreturnNone

总结

刷题+写总结还是挺上瘾的，开始每天愿意写题目了，写博客是一个自我消化自我解读的过程。计划同时把灵神的基础算法题也写完，希望做得到吧。