（本合集全部为Go语言实现）
Leetcode24
状态：秒了
实现过程中的难点：对组内两个节点的指针指向流转需要倒腾明白。临时头结点真的很有用
个人写法
func swapPairs(head *ListNode) *ListNode {
tmpHead := &ListNode{-1, head}
ptr := tmpHead
for ptr.Next != nil && ptr.Next.Next != nil {
tmp := ptr.Next
ptr.Next = tmp.Next
tmp.Next = tmp.Next.Next
ptr.Next.Next = tmp
ptr = ptr.Next.Next
}
return tmpHead.Next
}
Leetcode19
状态：秒了
实现过程中的难点：需要自己模拟出最终状态，确保左指针是待删除节点的前一个节点
个人写法
func removeNthFromEnd(head *ListNode, n int) *ListNode {
tmpHead := &ListNode{-1, head}
post := tmpHead
pre := tmpHead
for i := 0; i < n; i++ {
pre = pre.Next
}
for pre.Next != nil {
pre = pre.Next
post = post.Next
}
post.Next = post.Next.Next
return tmpHead.Next
}
Leetcode面试题02.07
状态：改了几次，有些情况没考虑到位
实现过程中的难点：主要是巧妙写法的思路能不能想出来
个人写法
暴力写法应该是同步遍历两各分支，并同时将分支节点指针存到
Set中，如果其中一个分支的指针在另一个分支的Set中出现了，那么该节点就是相交点
func getIntersectionNode(headA, headB *ListNode) *ListNode {
if headA == nil || headB == nil {
return nil
}
ptr1, ptr2 := headA, headB
for ptr1 != ptr2 {
if ptr1 == nil {
ptr1 = headB
} else {
ptr1 = ptr1.Next
}
if ptr2 == nil {
ptr2 = headA
} else {
ptr2 = ptr2.Next
}
}
return ptr1
}
Leetcode142
状态：记得这道是快慢指针，但是忘了过程是怎么写的了。看了代码随想录的B站视频复习了一下
实现过程中的难点：其实是数学问题，直接想不太好想，需要基于数学公式模拟过程
过程分析
快慢指针过程推导：两个指针初始状态都指向头节点，fast指针每次走两步，slow指针每次走一步
判断链表是否有环
- 由于
fast一定在前，所以如果fast先探测到空，那么链表一定无环 - 如果链表有环，那么两指针一定会进入环，此时
fast相对slow的速度为1，所以两者最终一定会相遇，而不会出现fast跳过slow的情景。这可能起初看到此题的一个疑问
环入口点的搜索
设无环部分长度为x，环内部分中，入口到相遇点长度为y，相遇点距离入口点长度为z
- 由快慢指针之间的速度关系可以得到：
2 * (x + y) = x + y + k * (y + z)- 推导得：
x = (k - 1) * y + k * z - 为什么有个参数
k？你可能会认为，从慢指针进入环到两者相遇，快指针可能是在走了k圏之后，才和慢指针相遇的，但是此时慢指针已经进入环了，首次相遇就会跳出循环，所以k = 1 - 于是
x = z，这就是结题的关键条件了
- 推导得：
个人写法
func detectCycle(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return nil
}
fast, slow := head.Next.Next, head.Next
for fast != slow {
if fast == nil || fast.Next == nil {
return nil
}
fast = fast.Next.Next
slow = slow.Next
}
fast = head
for fast != slow {
fast = fast.Next
slow = slow.Next
}
return fast
}
今日收获
- 主要是最后一道题的思路没有想到，算是复习了一下
学习时长：2小时左右比较分散