链表基础：链表反转、合并两个有序链表、环形链表检测、删除链表倒数第N个节点

链表这个数据结构，说实话，在iOS日常业务开发中用得不多。但面试时它绝对是高频考点。为什么？因为链表操作特别考验指针操作和边界处理能力。我当年面试大厂时，四道题里有两道是链表题。

今天咱们就把链表最经典的四个操作一次性讲透。你想想看，掌握了这些，面试时至少能顶住一轮技术面。

一、链表反转

链表反转，说白了就是把一个单向链表的方向全部调转。比如 1→2→3→4→5 变成 5→4→3→2→1。

我个人习惯用迭代法，因为空间复杂度是 O(1)，而且逻辑清晰。

// 迭代法反转链表
func reverseList(_ head: ListNode?) -> ListNode? {
    var prev: ListNode? = nil
    var current = head
    
    while current != nil {
        let nextTemp = current?.next  // 先保存下一个节点
        current?.next = prev          // 反转指针
        prev = current                // 前驱节点后移
        current = nextTemp            // 当前节点后移
    }
    
    return prev
}

这里有个坑，我刚开始学的时候踩过。就是 current?.next = prev 这一步执行后，原来的链表就断了。所以必须提前把下一个节点存起来。嗯，这里要注意顺序。

二、合并两个有序链表

合并两个有序链表，就是把两个已经排好序的链表合并成一个新的有序链表。比如 1→3→5 和 2→4→6，合并后是 1→2→3→4→5→6。

这道题有两种主流解法：递归和迭代。我个人更推荐迭代法，因为递归虽然代码短，但面试时容易把递归深度说漏了。

// 迭代法合并两个有序链表
func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    let dummy = ListNode(0)  // 哨兵节点
    var current = dummy
    var p1 = l1
    var p2 = l2
    
    while p1 != nil && p2 != nil {
        if p1!.val < p2!.val {
            current.next = p1
            p1 = p1?.next
        } else {
            current.next = p2
            p2 = p2?.next
        }
        current = current.next!
    }
    
    // 处理剩余节点
    current.next = p1 ?? p2
    
    return dummy.next
}

为什么用哨兵节点？说白了就是为了避免处理头节点的特殊情况。我在项目中处理链表合并时，哨兵节点帮我省了不少边界判断的麻烦。

三、环形链表检测

环形链表检测，就是判断一个链表里有没有环。比如 1→2→3→4→2（回到2），这就是个环。

这道题最经典的解法就是快慢指针，也叫 Floyd 判圈算法。我当年第一次看到这个解法时，觉得太巧妙了。

// 快慢指针检测环形链表
func hasCycle(_ head: ListNode?) -> Bool {
    var slow = head
    var fast = head
    
    while fast != nil && fast?.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
        
        if slow === fast {  // 注意这里用 === 比较引用
            return true
        }
    }
    
    return false
}

为什么会这样？想象一下两个人在操场上跑步，快的人跑得快，慢的人跑得慢。如果跑道是环形的，快的人迟早会追上慢的人。如果跑道是直线的，快的人先到终点，永远不会相遇。

四、删除链表倒数第N个节点

删除倒数第 N 个节点，比如链表 1→2→3→4→5，删除倒数第 2 个节点，结果变成 1→2→3→5。

这道题最直观的做法是先遍历一遍得到链表长度，再遍历到倒数第 N 个节点删除。但更好的做法是用双指针，一次遍历搞定。

// 双指针法删除倒数第N个节点
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    let dummy = ListNode(0)
    dummy.next = head
    var fast: ListNode? = dummy
    var slow: ListNode? = dummy
    
    // 快指针先走 n+1 步
    for _ in 0...n {
        fast = fast?.next
    }
    
    // 快慢指针一起走
    while fast != nil {
        fast = fast?.next
        slow = slow?.next
    }
    
    // 删除 slow 的下一个节点
    slow?.next = slow?.next?.next
    
    return dummy.next
}

这里有个细节：快指针为什么要先走 n+1 步？因为我们要让慢指针指向待删除节点的前一个节点，这样才能执行删除操作。我曾经在面试时被问到这个问题，当时差点答错。

总结对比

题目	核心思想	时间复杂度	空间复杂度
链表反转	迭代法，改变指针方向	O(n)	O(1)
合并有序链表	哨兵节点 + 双指针	O(n+m)	O(1)
环形链表检测	快慢指针	O(n)	O(1)
删除倒数第N个节点	双指针 + 哨兵节点	O(n)	O(1)

这四道题，说白了就是链表操作的基本功。你想想看，反转链表考的是指针操作，合并链表考的是归并思想，环形检测考的是快慢指针，删除节点考的是双指针技巧。掌握了这些，面试时遇到链表题基本都能应对。

最后说一句，我建议你把这些代码手写几遍。光看是记不住的，只有亲手写过，面试时才能信手拈来。