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

一、写在前面链表相关的题在面试中出现的频率非常高。因为链表操作涉及指针能考察对内存和引用的理解而且代码量不大适合手写。这一篇我们不讲链表的增删改查了专门讲几个经典题。每个题我都会先讲思路再给代码最后分析复杂度。二、准备工作为了不依赖上一篇的链表结构这篇我们直接用节点结构体来操作。假设链表是带头结点的但为了代码简洁很多题的实现用不带头结点的版本更直观。节点定义ctypedef 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的下一个节点防止断链步骤初始化prev NULL,cur head循环直到cur NULL用next保存cur-next将cur-next指向prev反转方向prev移动到curcur移动到next循环结束后prev就是新链表的头画个图理解text初始 prev NULL cur 1 → 2 → 3 → NULL 第一步处理节点1 next 2 1 → NULLcur-next prev prev 1 cur 2 当前状态 prev 1 → NULL cur 2 → 3 → NULL 第二步处理节点2 next 3 2 → 1 → NULLcur-next prev prev 2 cur 3 ... 直到 cur NULL 最终 prev 3 → 2 → 1 → NULL3.3 代码实现cPNode 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中间节点是44.2 思路分析经典解法快慢指针。快指针每次走两步慢指针每次走一步当快指针走到末尾时慢指针刚好在中间为什么能到中间快指针速度是慢指针的两倍相同时间内快指针走的路程是慢指针的两倍快指针到末尾时慢指针正好走了一半处理偶数个节点如果快指针的next是 NULL说明链表长度为奇数慢指针就是中间如果快指针本身是 NULL说明链表长度为偶数慢指针是第二个中间节点4.3 代码实现cPNode 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 → 5k2返回4。5.2 思路分析同样用快慢指针但这次两个指针保持固定的距离。步骤快指针先走k步然后快慢指针一起走直到快指针到末尾此时慢指针指向的就是倒数第k个节点边界处理如果链表长度小于k返回NULL5.3 代码实现cPNode 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 代码实现cint 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 环的入口进阶如果链表有环怎么找到环的入口这是进阶题思路如下先判断是否有环找到相遇点将慢指针放回起点快指针留在相遇点两个指针都每次走一步再次相遇的位置就是环的入口cPNode 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八、小结这一篇讲了四个经典链表题核心技巧都是指针操作和快慢指针题目核心技巧时间复杂度反转链表三个指针迭代O(n)找中间节点快慢指针O(n)找倒数第k个快慢指针固定距离O(n)判断是否有环快慢指针O(n)快慢指针的套路找中间快两步慢一步找倒数第k快先走k步判环快两步慢一步相遇则有环这些题面试中出现频率很高建议自己多写几遍把指针的指向关系搞清楚。九、思考题反转链表有没有递归写法尝试实现一下。如果链表有环如何判断环的长度找倒数第k个节点如果k1相当于找什么如果k等于链表长度呢快慢指针找中间节点为什么偶数个节点时返回的是第二个中间节点如果想返回第一个中间节点代码怎么改欢迎在评论区讨论你的答案。