题目 1：反转单链表

题目描述

给你单链表的头节点 head，请你反转链表，并返回反转后的链表。分别用迭代和递归两种方式实现。

解题思路

迭代法（三指针）： 用三个指针 prev、curr、next 遍历链表，逐个改变节点的 next 指向，最终 prev 成为新的头节点。

递归法： 递归反转当前节点之后的子链表，然后将当前节点的下一个节点的 next 指向当前节点，当前节点的 next 置空。

代码实现

cpp

运行

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 迭代法
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* next = curr->next; // 保存下一个节点
        curr->next = prev;           // 反转指针
        prev = curr;                 // prev后移
        curr = next;                 // curr后移
    }
    return prev;
}

// 递归法
ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

复杂度分析

• 迭代法：时间 O (n)，空间 O (1)
• 递归法：时间 O (n)，空间 O (n)（递归栈开销）

面试考点

链表基础必考题。面试官常延伸：反转链表的前 k 个节点？反转指定区间内的链表？

---

题目 2：链表中环的入口节点

题目描述

给定一个链表，判断链表中是否有环。如果有环，返回链表开始入环的第一个节点；如果链表无环，则返回 nullptr。

解题思路

快慢指针法（Floyd 判圈算法）：

1. 慢指针每次走 1 步，快指针每次走 2 步，若相遇则存在环
2. 相遇后，将其中一个指针移回起点，两个指针每次都走 1 步，再次相遇的位置就是环的入口

数学原理：设头节点到入口距离为 a，入口到相遇点距离为 b，相遇点回到入口距离为 c。相遇时快指针路程是慢指针 2 倍，可得 a + b + n(b+c) = 2(a+b)，化简得 a = c + (n-1)(b+c)，即从起点和相遇点同时出发，必然在入口相遇。

代码实现

cpp

运行

ListNode *detectCycle(ListNode *head) {
    ListNode* slow = head;
    ListNode* fast = head;
    // 第一步：判断是否有环
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            // 第二步：找入口节点
            fast = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return nullptr;
}

复杂度分析

• 时间复杂度：O (n)，两阶段遍历总长度不超过链表长度
• 空间复杂度：O (1)

面试考点

经典算法应用，重点考察数学推导能力。面试官常追问：为什么快指针每次走 2 步？走 3 步行不行？

---

题目 3：合并两个有序链表

题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解题思路

虚拟头节点 + 双指针： 创建一个虚拟头节点 dummy，用指针 cur 指向它，然后双指针分别遍历两个链表，每次取较小值的节点接到 cur 后面，直到其中一个链表遍历完，再把剩余链表直接接上。

代码实现

cpp

运行

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* dummy = new ListNode(0);
    ListNode* cur = dummy;
    while (list1 && list2) {
        if (list1->val <= list2->val) {
            cur->next = list1;
            list1 = list1->next;
        } else {
            cur->next = list2;
            list2 = list2->next;
        }
        cur = cur->next;
    }
    // 接上剩余部分
    cur->next = list1 ? list1 : list2;
    return dummy->next;
}

复杂度分析

• 时间复杂度：O (m+n)，m、n 为两个链表长度
• 空间复杂度：O (1)，仅创建一个虚拟头节点

面试考点

链表基础操作。延伸考点：合并 k 个有序链表怎么实现？递归写法怎么写？

---

题目 4：链表的倒数第 k 个节点

题目描述

输入一个链表，输出该链表中倒数第 k 个节点。

解题思路

快慢双指针： 快指针先走 k 步，然后快慢指针一起走，当快指针走到末尾时，慢指针正好指向倒数第 k 个节点。只需一次遍历即可完成。

代码实现

cpp

运行

ListNode* getKthFromEnd(ListNode* head, int k) {
    ListNode* fast = head;
    ListNode* slow = head;
    // 快指针先走k步
    for (int i = 0; i < k; i++) {
        if (!fast) return nullptr; // 链表长度不足k
        fast = fast->next;
    }
    // 同步前进
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

复杂度分析

• 时间复杂度：O (n)，仅一次遍历
• 空间复杂度：O (1)

面试考点

考察双指针在链表中的灵活应用。注意边界情况：k 为 0、k 大于链表长度、链表为空等。