题目 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 步快指针每次走 2 步若相遇则存在环相遇后将其中一个指针移回起点两个指针每次都走 1 步再次相遇的位置就是环的入口数学原理设头节点到入口距离为 a入口到相遇点距离为 b相遇点回到入口距离为 c。相遇时快指针路程是慢指针 2 倍可得a b n(bc) 2(ab)化简得a c (n-1)(bc)即从起点和相遇点同时出发必然在入口相遇。代码实现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 (mn)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 大于链表长度、链表为空等。谢谢