链表

解决链表问题的通用思路可以分为以下几个步骤：

1. 理解问题：首先要准确理解题目的要求，链表的类型（单链表、双链表等），以及是否有环。

2. 确定算法策略：根据问题的类型，决定是使用双指针、递归、迭代、哈希表等策略。

3. 边界条件处理：在编写代码之前，考虑链表为空、只有一个节点、只有两个节点等边界情况。

4. 编写代码：根据选定的策略编写代码，注意指针的移动和条件判断。

5. 测试用例：考虑各种可能的测试用例，包括边界情况，确保代码的鲁棒性。

下面是一些常见的链表问题和用 Go 语言编写的代码示例：

例 1：反转链表

反转链表是最基本的链表操作之一，可以用迭代或递归的方式来实现。

type ListNode struct {
    Val int
    Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    for curr != nil {
        nextTemp := curr.Next
        curr.Next = prev
        prev = curr
        curr = nextTemp
    }
    return prev
}

例 2：检测链表中是否有环

使用快慢指针的方法，如果快指针最终追上慢指针，则链表中存在环。

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
    slow := head
    fast := head.Next
    for fast != nil && fast.Next != nil {
        if slow == fast {
            return true
        }
        slow = slow.Next
        fast = fast.Next.Next
    }
    return false
}

例 3：合并两个排序的链表

将两个已排序的链表合并为一个新的排序链表。

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    current := dummy
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            current.Next = l1
            l1 = l1.Next
        } else {
            current.Next = l2
            l2 = l2.Next
        }
        current = current.Next
    }
    if l1 != nil {
        current.Next = l1
    } else {
        current.Next = l2
    }
    return dummy.Next
}

例 4：找到链表的中间节点

使用快慢指针找到链表的中间节点。

func middleNode(head *ListNode) *ListNode {
    slow := head
    fast := head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

在解决链表问题时，重要的是要熟练掌握指针的使用，理解每个节点和指针的关系，以及在操作过程中可能出现的边界情况。练习和理解这些基本问题后，对于更复杂的链表问题也会有很大帮助。