[Go] LeetCode 24.两两交换链表中的节点 19.删除链表的倒数第N个节点 面试题02.07.链表相交 142.环形链表 II

一、背景与问题

链表作为基础数据结构，在软件开发中广泛应用。这四个LeetCode题目分别涉及链表的常见操作：节点交换、倒数节点删除、链表相交查找、环形链表入口点定位。这些问题在实际开发中常出现在以下场景：

1. 数据结构设计：如构建链表缓存、链表队列等
2. 算法实现：如图的邻接表表示、树的序列化等
3. 系统底层开发：如内存管理、资源回收机制
4. 并发控制：如链表节点的原子操作

这些题目共同的特点是：需要对链表的指针操作有深刻理解，同时需要考虑边界条件、空指针、异常处理等场景。本文将深入分析这四个题目的核心原理，探讨其在实际开发中的应用价值和注意事项。

二、基本原理

1. 链表节点交换（LeetCode 24）

核心原理：通过指针的链式操作，逐个交换相邻节点。关键点在于保持链表的连续性，处理头节点的特殊情况。

2. 删除倒数第N个节点（LeetCode 19）

核心原理：利用快慢指针法，先让快指针移动N步，再同时移动快慢指针，最终慢指针指向要删除的节点。需要特别注意空链表和头节点删除的边界情况。

3. 链表相交（面试题02.07）

核心原理：通过哈希表存储节点，或者利用双指针法（先移动长链表指针到等长位置，再同时移动指针）来判断相交点。

4. 环形链表 II（LeetCode 142）

核心原理：使用快慢指针法，当快指针追上慢指针时，说明存在环。进一步通过数学推导找到环的入口点。

三、环境准备

package main

import (
    "fmt"
    "os"
)

// 定义链表节点
type ListNode struct {
    Val  int
    Next *ListNode
}

// 创建链表
func createList(nums []int) *ListNode {
    if len(nums) == 0 {
        return nil
    }
    head := &ListNode{Val: nums[0]}
    current := head
    for i := 1; i < len(nums); i++ {
        current.Next = &ListNode{Val: nums[i]}
        current = current.Next
    }
    return head
}

// 打印链表
func printList(head *ListNode) {
    for head != nil {
        fmt.Print(head.Val, " -> ")
        head = head.Next
    }
    fmt.Println("nil")
}

四、核心实现

1. 两两交换链表中的节点（LeetCode 24）

// 两两交换链表中的节点
func swapPairs(head *ListNode) *ListNode {
    dummyHead := &ListNode{Val: 0, Next: head}
    current := dummyHead
    
    for current.Next != nil && current.Next.Next != nil {
        // 保存当前节点的下一个节点
        first := current.Next
        second := current.Next.Next
        
        // 交换指针
        current.Next = second
        first.Next = second.Next
        second.Next = first
        
        // 移动指针
        current = current.Next.Next
    }
    
    return dummyHead.Next
}

关键代码解释：

• 创建虚拟头节点dummyHead处理头节点特殊情况
• 使用双指针first和second保存待交换的两个节点
• 通过指针重定向完成交换操作
• 通过current指针移动完成遍历

2. 删除链表的倒数第N个节点（LeetCode 19）

// 删除链表的倒数第N个节点
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummyHead := &ListNode{Val: 0, Next: head}
    fast, slow := dummyHead, dummyHead
    
    // 快指针先走n步
    for i := 0; i < n; i++ {
        fast = fast.Next
    }
    
    // 快慢指针同时移动
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    
    // 删除节点
    slow.Next = slow.Next.Next
    return dummyHead.Next
}

关键代码解释：

• 使用虚拟头节点处理头节点删除的特殊情况
• 快指针先走n步，确保慢指针最终指向要删除的节点
• 删除节点时需要调整指针链接

3. 链表相交（面试题02.07）

// 链表相交
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    
    // 计算链表长度
    lenA, lenB := 0, 0
    for current := headA; current != nil; current = current.Next {
        lenA++
    }
    for current := headB; current != nil; current = current.Next {
        lenB++
    }
    
    // 调整指针位置
    for lenA > lenB {
        headA = headA.Next
        lenA--
    }
    for lenB > lenA {
        headB = headB.Next
        lenB--
    }
    
    // 同步移动指针
    for headA != headB {
        headA = headA.Next
        headB = headB.Next
    }
    return headA
}

关键代码解释：

• 通过遍历计算链表长度
• 通过调整指针位置使两个链表长度相等
• 同步移动指针直到找到相交点

五、完整案例

func main() {
    // 创建测试链表
    list1 := createList([]int{1, 2, 3, 4, 5})
    list2 := createList([]int{6, 1, 2, 3})
    
    // 链表相交测试
    list2.Next = list1.Next.Next // 让两个链表在节点3处相交
    
    fmt.Println("原始链表：")
    printList(list1)
    printList(list2)
    
    // 查找相交点
    intersectNode := getIntersectionNode(list1, list2)
    fmt.Printf("相交点：%v\n", intersectNode.Val)
    
    // 删除倒数第N个节点
    fmt.Println("删除倒数第2个节点后：")
    list1 = removeNthFromEnd(list1, 2)
    printList(list1)
    
    // 两两交换节点
    fmt.Println("交换后：")
    list1 = swapPairs(list1)
    printList(list1)
    
    // 环形链表测试
    list3 := createList([]int{1, 2, 3, 4, 5})
    list3.Next.Next.Next.Next.Next = list3.Next // 创建环
    
    fmt.Println("环形链表：")
    printList(list3)
    
    // 找到环入口点
    entryNode := detectCycle(list3)
    fmt.Printf("环入口点：%v\n", entryNode.Val)
}

六、源码解析

1. 环形链表II（LeetCode 142）

// 环形链表 II
func detectCycle(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    
    // 快慢指针
    slow, fast := head, head
    
    // 找到快慢指针相遇点
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            break
        }
    }
    
    // 如果没有环
    if slow != fast {
        return nil
    }
    
    // 计算环的长度
    length := 0
    for slow.Next != fast {
        slow = slow.Next
        length++
    }
    
    // 移动指针找到入口点
    slow = slow.Next
    for i := 0; i < length; i++ {
        slow = slow.Next
    }
    
    return slow
}

关键代码解释：

• 快慢指针法寻找相遇点
• 计算环的长度时需要从相遇点开始遍历
• 通过数学推导找到入口点：slow = slow.Next后，让快指针走环的长度

七、进阶使用

在实际开发中，这些链表操作可以用于：

1. 缓存系统：使用链表实现LRU缓存，通过删除倒数节点实现最近最少使用策略
2. 资源管理：通过链表相交检测实现内存泄漏检测
3. 并发控制：在锁机制中使用环形链表实现等待队列

优化方案

1. 空间优化：所有解法都使用O(1)空间复杂度
2. 时间优化：所有解法都使用O(n)时间复杂度
3. 多线程安全：在链表操作时需要加锁，避免竞态条件

八、性能与工程实践

1. 性能分析

2. 异常处理

• 链表为空时的处理
• 删除头节点时的处理
• 环形链表的边界条件处理

3. 安全风险

• 指针越界访问（如current.Next时未检查current是否为nil）
• 空指针解引用（如head.Next时未检查head是否为nil）
• 无限循环（如环形链表未正确处理）

九、常见问题与踩坑

1. 常见错误

错误示例：

// 错误的链表相交实现
func getIntersectionNodeWrong(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    
    for headA != nil && headB != nil {
        if headA == headB {
            return headA
        }
        headA = headA.Next
        headB = headB.Next
    }
    return nil
}

错误原因：

• 没有处理链表长度不一致的情况
• 快慢指针法未正确实现

解决办法：

• 使用双指针法调整链表长度
• 在循环中处理指针移动

2. 常见坑点

十、最佳实践

1. 使用虚拟头节点：统一处理头节点删除的特殊情况
2. 使用快慢指针法：高效处理链表长度相关问题
3. 边界条件检查：在操作指针前检查空指针
4. 数学推导：在环形链表问题中使用数学公式计算入口点
5. 代码注释：对关键指针操作添加详细注释
6. 单元测试：为每个函数编写测试用例覆盖边界情况

十一、总结

这四个链表问题展示了Go语言在处理指针操作时的灵活性和效率。通过深入理解指针的链式操作原理，我们能够设计出高效的链表处理算法。在实际开发中，这些技术可以用于缓存系统、资源管理等场景，但需要注意处理边界条件、指针越界等问题。

需要特别注意的是：链表操作虽然在某些场景下效率较高，但在需要频繁随机访问或数据量较大的情况下，应考虑使用数组或更高效的数据结构。同时，多线程环境下需要特别注意指针的同步和安全问题。

这些算法的掌握不仅能帮助解决LeetCode题目，更能提升我们对底层数据结构的理解，为开发高性能系统打下坚实基础。