24 两两交换节点
func swapPairs(head *ListNode) *ListNode {
// 思路 涉及到链表增删改操作，优先考虑使用虚拟头节点 此处为双指针加上虚拟头节点
if head == nil || head.Next == nil {
return head
}
var dummyHead = &ListNode{0, head}
var prev = dummyHead
for prev.Next != nil && prev.Next.Next != nil { // 同时考虑奇数长度链表和偶数长度链表终止条件
node1 := prev.Next
node2 := prev.Next.Next
node1.Next = node2.Next
node2.Next = node1
prev.Next = node2
prev = node1
}
return dummyHead.Next
}
时间 跳着便利链表本质上n/2 n 空间 有限单变量 1
func swapPairs(head *ListNode) *ListNode {
// 思路 尝试根据双指针 写出 递归
if head == nil || head.Next == nil {
return head
}
var dummyHead = &ListNode{0, head}
cur := dummyHead
swap(cur)
return dummyHead.Next
}
func swap(cur *ListNode) {
if cur.Next == nil || cur.Next.Next == nil { // 根据外层for循环判断递归终止条件
return
}
// 循环体的交换节点结构
node1 := cur.Next
node2 := cur.Next.Next
node1.Next = node2.Next
node2.Next = node1
cur.Next = node2
// 递归条件，即变量的迭代条件prev = node1
swap(node1)
return
}
19 删除链表倒数第n个节点
func removeNthFromEnd(head *ListNode, n int) *ListNode {
// 思路 链表的删除操作，优先考虑虚拟头节点
// 然后尝试双指针，看了视频后的思路很清晰，重点 难点是n就是两个指针之间的间隔，cur == nil 就删除 pre
var dummyHead = &ListNode{0, head}
var pre, cur = dummyHead, dummyHead
for i:=0 ; i<n; i++ { // 此处作用往后跳n个节点，题目已经说明n<size，所以不考虑越界情况
cur = cur.Next
}
for cur.Next != nil { // cur == nil 循环终止，删除pre， 但是这样写我们没办法处理删除将pre上一个元素与pre之后连接，除非单独变量保存，所以这里采用cur.next != nil, pre存储上一个变量，要删除pre.Next
cur = cur.Next
pre = pre.Next // pre 永远走在cur之后，所以不会空指针
}
// 遍历完成，此时pre位于删除元素上一个节点
pre.Next = pre.Next.Next // 直接next指向删除元素下一个节点，删除完成
return dummyHead.Next
}
// 时间 遍历整个链表 n-常数间隔 = n 空间 有限单变量 1
160 判断链表相交节点
func getIntersectionNode(headA, headB *ListNode) *ListNode {
// 思路 类似双指针 快慢指针 快指针遍历链表a, 慢指针遍历链表b, 如果节点内存地址相等，视为相交
for headA != nil {
cur := headB // 由于是指针类型引用，所以这里的内存地址相同与head2
for cur != nil { // 这里使用cur而不是用head2是因为内部便利之后head已经变成尾节点了，不能直接使用了
if cur == headA { // 判断内存地址是否相等
return headA
}
cur = cur.Next
}
headA = headA.Next
}
return nil
}
// 思考
为甚么判断内存地址 &cur == &headA 这样子写是错误的？
因为 cur, head 是指针，指向的是其他变量的内存地址，但是指针也是变量，也有自己的内存地址，如果对指针再取指针，那么取得就是两个指针变量的内存地址，就不是我们想要的对比保存变量的内存地址结果了
时间 m*n 空间 1
-
循环链表的思路（时间复杂度m+n）
-
数学逻辑解释
假设链表 A 的长度为 (m)，链表 B 的长度为 (n)，它们在节点 (C) 处相交。链表 A 在相交前的部分长度为 (a)，链表 B 在相交前的部分长度为 (b)，相交部分的长度为 (c)。
因此，我们有：
[ m = a + c ]
[ n = b + c ]
- 双指针方法的逻辑
初始化：两个指针 (pA) 和 (pB) 分别指向链表 A 和链表 B 的头节点。
遍历链表：两个指针同时向前移动，如果到达链表末尾，则重定位到另一个链表的头节点。
相遇：由于两个指针遍历的总长度相同，最终会在相交节点处相遇。
详细解释
当 (pA) 遍历完链表 A 后，它将重定位到链表 B 的头节点，并继续遍历链表 B。
当 (pB) 遍历完链表 B 后，它将重定位到链表 A 的头节点，并继续遍历链表 A。
经过第一次遍历后，两个指针分别走过的路径长度为：
[ pA: a + c + b ]
[ pB: b + c + a ]
由于 (a + c + b = b + c + a)，因此两个指针在第二次遍历中会在相交节点 (C) 处相遇。
- 数学推导
我们可以通过数学推导来验证这种方法的正确性：
第一次遍历：
指针 (pA) 走过的路径长度为 (a + c)，然后重定位到链表 B。
指针 (pB) 走过的路径长度为 (b + c)，然后重定位到链表 A。
第二次遍历：
指针 (pA) 继续走过链表 B 的长度 (b)。
指针 (pB) 继续走过链表 A 的长度 (a)。
由于两个指针走过的总路径长度相同，最终会在相交节点 (C) 处相遇。
func getIntersectionNode(headA, headB *ListNode) *ListNode {
// 思路 循环链表的思路。只需要不到两圈就能查找到相交点
nodeA, nodeB := headA, headB
for nodeA != nodeB { // 未到相交点
// 遍历链表a
if nodeA == nil { // 遍历完a遍历b
nodeA = headB
}else{
nodeA = nodeA.Next
}
// b同理
if nodeB == nil {
nodeB = headA
}else{
nodeB = nodeB.Next
}
}
return nodeA
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
// 思路 根据双指针写出递归
return checkInter(headA, headB, headA, headB)
}
func checkInter(nodeA, nodeB, headA, headB *ListNode) *ListNode {
if nodeA == nodeB { // 循环结束条件就是递归终止条件
return nodeA
}
// 遍历链表a
if nodeA == nil { // 遍历完a遍历b
nodeA = headB
}else{
nodeA = nodeA.Next
}
// b同理
if nodeB == nil {
nodeB = headA
}else{
nodeB = nodeB.Next
}
return checkInter(nodeA, nodeB, headA, headB)
}
142 环形链表入口
-
快慢指针相遇：快指针一次移动两个节点，慢指针一次移动一个节点，快指针和慢指针在环内某个节点相遇时，快指针已经比慢指针多走了一个或多个完整的环。
-
相遇后的距离关系：由于快指针比慢指针多走了一个或多个完整的环，我们可以得出从头节点到环入口的距离 a 等于从相遇点沿着环再走 c 的距离。
-
找到环的入口：当快指针和慢指针相遇后，将快指针重新指向链表头节点，然后快指针和慢指针每次都移动一步。由于从头节点到环入口的距离等于从相遇点再走到环入口的距离，因此它们最终会在环的入口相遇。
func detectCycle(head *ListNode) *ListNode {
// 思路 快慢指针方法
// 极端情况处理
if head == nil || head.Next == nil {
return nil
}
fast, slow := head.Next.Next, head.Next
for fast != slow { // 循环结束条件，快慢指针相交，此时快指针移动距离 两倍于 慢指针移动距离
if slow == nil || fast == nil || fast.Next == nil { // 无环 fast.Next == nil 这里判断防止 fast = fast.Next.Next
return nil
}
slow = slow.Next
fast = fast.Next.Next
}
// 此时fast，slow相交，然后新指针从头节点遍历，头到环入口位置 = 慢指针移动常数圈 + 交点到入口距离，所以会相交于入口位置
fast = head
for fast != slow { // 此时已经判断有环，所以不用考虑nil边界情况
fast = fast.Next
slow = slow.Next
}
return fast // return slow
}