【数据结构与算法】第7篇：线性表（三）：单链表的经典面试题（反转、找中间节点）

一、写在前面

链表相关的题，在面试中出现的频率非常高。因为链表操作涉及指针，能考察对内存和引用的理解，而且代码量不大，适合手写。

这一篇我们不讲链表的增删改查了，专门讲几个经典题。每个题我都会先讲思路，再给代码，最后分析复杂度。

二、准备工作

为了不依赖上一篇的链表结构，这篇我们直接用节点结构体来操作。假设链表是带头结点的，但为了代码简洁，很多题的实现用不带头结点的版本更直观。

节点定义：

c

typedef struct Node { int data; struct Node *next; } Node, *PNode;

辅助函数：创建一个链表（方便测试）

c

// 根据数组创建链表（不带头结点，返回头指针） PNode createList(int arr[], int n) { if (n == 0) return NULL; PNode head = (PNode)malloc(sizeof(Node)); head->data = arr[0]; head->next = NULL; PNode tail = head; for (int i = 1; i < n; i++) { PNode newNode = (PNode)malloc(sizeof(Node)); newNode->data = arr[i]; newNode->next = NULL; tail->next = newNode; tail = newNode; } return head; } // 打印链表 void printList(PNode head) { PNode cur = head; while (cur != NULL) { printf("%d", cur->data); if (cur->next != NULL) printf(" -> "); cur = cur->next; } printf("\n"); }

三、题1：反转链表

3.1 题目描述

反转一个单链表。例如：1 → 2 → 3 → 4 → NULL，反转后变成 4 → 3 → 2 → 1 → NULL。

3.2 思路分析

反转链表的核心是改变指针的指向。需要三个指针：

• prev：指向已反转部分的新头

• cur：指向当前要处理的节点

• next：保存cur的下一个节点，防止断链

步骤：

1. 初始化prev = NULL,cur = head

2. 循环直到cur == NULL：

   • 用next保存cur->next

   • 将cur->next指向prev（反转方向）

   • prev移动到cur

   • cur移动到next

3. 循环结束后，prev就是新链表的头

画个图理解：

text

初始： prev = NULL cur = 1 → 2 → 3 → NULL 第一步（处理节点1）： next = 2 1 → NULL（cur->next = prev） prev = 1 cur = 2 当前状态： prev = 1 → NULL cur = 2 → 3 → NULL 第二步（处理节点2）： next = 3 2 → 1 → NULL（cur->next = prev） prev = 2 cur = 3 ... 直到 cur = NULL 最终 prev = 3 → 2 → 1 → NULL

3.3 代码实现

c

PNode reverseList(PNode head) { PNode prev = NULL; PNode cur = head; PNode next = NULL; while (cur != NULL) { next = cur->next; // 保存下一个节点 cur->next = prev; // 反转当前节点的指针 prev = cur; // prev后移 cur = next; // cur后移 } return prev; // prev就是新链表的头 }

3.4 复杂度分析

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

• 空间复杂度：O(1)，只用三个指针

四、题2：找中间节点

4.1 题目描述

给定一个非空单链表，返回链表的中间节点。如果有两个中间节点（偶数个节点），返回第二个中间节点。

例如：1 → 2 → 3 → 4 → 5，中间节点是3
例如：1 → 2 → 3 → 4 → 5 → 6，中间节点是4

4.2 思路分析

经典解法：快慢指针。

• 快指针每次走两步

• 慢指针每次走一步

• 当快指针走到末尾时，慢指针刚好在中间

为什么能到中间？

• 快指针速度是慢指针的两倍，相同时间内快指针走的路程是慢指针的两倍

• 快指针到末尾时，慢指针正好走了一半

处理偶数个节点：

• 如果快指针的next是 NULL，说明链表长度为奇数，慢指针就是中间

• 如果快指针本身是 NULL，说明链表长度为偶数，慢指针是第二个中间节点

4.3 代码实现

c

PNode findMiddle(PNode head) { if (head == NULL) return NULL; PNode slow = head; PNode fast = head; // 快指针每次走两步，慢指针走一步 while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; }

4.4 复杂度分析

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

• 空间复杂度：O(1)，只用两个指针

五、题3：找倒数第k个节点

5.1 题目描述

找到单链表的倒数第k个节点。例如：1 → 2 → 3 → 4 → 5，k=2，返回4。

5.2 思路分析

同样用快慢指针，但这次两个指针保持固定的距离。

步骤：

1. 快指针先走k步

2. 然后快慢指针一起走，直到快指针到末尾

3. 此时慢指针指向的就是倒数第k个节点

边界处理：

• 如果链表长度小于k，返回NULL

5.3 代码实现

c

PNode findKthFromEnd(PNode head, int k) { if (head == NULL || k <= 0) return NULL; PNode fast = head; PNode slow = head; // 快指针先走k步 for (int i = 0; i < k; i++) { if (fast == NULL) return NULL; // 链表长度小于k fast = fast->next; } // 一起走，直到fast到末尾 while (fast != NULL) { slow = slow->next; fast = fast->next; } return slow; }

5.4 复杂度分析

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

• 空间复杂度：O(1)

六、题4：判断链表是否有环

6.1 题目描述

判断一个单链表中是否有环。有环的意思是：某个节点的next指向了链表中之前的节点，形成循环。

6.2 思路分析

还是快慢指针！

• 快指针每次走两步，慢指针每次走一步

• 如果没有环，快指针最终会走到NULL

• 如果有环，快慢指针会相遇（快指针追上慢指针）

为什么一定会相遇？
想象一下，在环里，快指针每次比慢指针多走一步。假设慢指针进环时，快指针在环的某个位置，它们之间的距离是d。每走一步，距离减少1，所以最多走d步就会相遇。

6.3 代码实现

c

int hasCycle(PNode head) { if (head == NULL) return 0; PNode slow = head; PNode fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) { return 1; // 有环 } } return 0; // 无环 }

6.4 环的入口（进阶）

如果链表有环，怎么找到环的入口？这是进阶题，思路如下：

• 先判断是否有环，找到相遇点

• 将慢指针放回起点，快指针留在相遇点

• 两个指针都每次走一步，再次相遇的位置就是环的入口

c

PNode findCycleEntry(PNode head) { if (head == NULL) return NULL; PNode slow = head; PNode fast = head; // 先判断是否有环，找到相遇点 while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) { // 有环，找入口 slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; } } return NULL; // 无环 }

七、完整测试代码

c

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node, *PNode; PNode createList(int arr[], int n) { if (n == 0) return NULL; PNode head = (PNode)malloc(sizeof(Node)); head->data = arr[0]; head->next = NULL; PNode tail = head; for (int i = 1; i < n; i++) { PNode newNode = (PNode)malloc(sizeof(Node)); newNode->data = arr[i]; newNode->next = NULL; tail->next = newNode; tail = newNode; } return head; } void printList(PNode head) { PNode cur = head; while (cur != NULL) { printf("%d", cur->data); if (cur->next != NULL) printf(" -> "); cur = cur->next; } printf("\n"); } PNode reverseList(PNode head) { PNode prev = NULL; PNode cur = head; PNode next = NULL; while (cur != NULL) { next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; } PNode findMiddle(PNode head) { if (head == NULL) return NULL; PNode slow = head; PNode fast = head;

PNode fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; } PNode findKthFromEnd(PNode head, int k) { if (head == NULL || k <= 0) return NULL; PNode fast = head; PNode slow = head; for (int i = 0; i < k; i++) { if (fast == NULL) return NULL; fast = fast->next; } while (fast != NULL) { slow = slow->next; fast = fast->next; } return slow; } int main() { int arr[] = {1, 2, 3, 4, 5}; PNode head = createList(arr, 5); printf("原链表: "); printList(head); // 反转 PNode reversed = reverseList(head); printf("反转后: "); printList(reversed); // 找中间节点（注意：原链表已经被反转了，所以重新建一个） PNode head2 = createList(arr, 5); PNode mid = findMiddle(head2); printf("中间节点: %d\n", mid->data); // 找倒数第2个 PNode kth = findKthFromEnd(head2, 2); printf("倒数第2个: %d\n", kth->data); // 测试偶数个节点 int arr2[] = {1, 2, 3, 4, 5, 6}; PNode head3 = createList(arr2, 6); PNode mid2 = findMiddle(head3); printf("偶数链表中间节点: %d\n", mid2->data); return 0; }

运行结果：

text

原链表: 1 -> 2 -> 3 -> 4 -> 5 反转后: 5 -> 4 -> 3 -> 2 -> 1 中间节点: 3 倒数第2个: 4 偶数链表中间节点: 4

八、小结

这一篇讲了四个经典链表题，核心技巧都是指针操作和快慢指针：

快慢指针的套路：

• 找中间：快两步，慢一步

• 找倒数第k：快先走k步

• 判环：快两步，慢一步，相遇则有环

这些题面试中出现频率很高，建议自己多写几遍，把指针的指向关系搞清楚。

九、思考题

1. 反转链表有没有递归写法？尝试实现一下。

2. 如果链表有环，如何判断环的长度？

3. 找倒数第k个节点，如果k=1，相当于找什么？如果k等于链表长度呢？

4. 快慢指针找中间节点，为什么偶数个节点时返回的是第二个中间节点？如果想返回第一个中间节点，代码怎么改？

欢迎在评论区讨论你的答案。