欢迎来到李耶的频道【LeetCode面试题】。
反转链表
题目
给你单链表的头节点head，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]输入：head = [1,2] 输出：[2,1]输入：head = [] 输出：[]解法一：双指针迭代
思路：使用prev和curr两个指针，prev指向当前节点的前一个节点，curr指向当前节点。遍历链表，将当前节点的next指向前一个节点，然后两个指针同时后移，直到遍历结束。这是最经典、最推荐面试手写的解法。
functionreverseList(head){letprev=null;letcurr=head;while(curr!==null){constnext=curr.next;// 保存下一个节点curr.next=prev;// 反转指针prev=curr;// prev 后移curr=next;// curr 后移}returnprev;}- 时间复杂度：O(n)，遍历一次链表
- 空间复杂度：O(1)，只使用了常数个指针变量
- 优势：最实用，性能最优，面试中最稳妥的写法
解法二：递归
思路：递归的核心思想是假设head.next之后的链表已经被反转好了，然后只需要处理head和head.next之间的指针关系。递归的终止条件是链表为空或只有一个节点。
functionreverseList(head){// 递归终止条件：空链表或只有一个节点if(head===null||head.next===null){returnhead;}// 递归反转 head.next 之后的链表，返回新的头节点constnewHead=reverseList(head.next);// 让 head.next 指向 head，完成反转head.next.next=head;head.next=null;returnnewHead;}- 时间复杂度：O(n)，每个节点访问一次
- 空间复杂度：O(n)，递归调用栈的深度取决于链表长度
- 优势：代码最简洁，体现了递归的优雅，但要注意链表过长可能导致栈溢出
解法三：解构赋值（ES6 语法糖）
思路：本质上还是双指针法，但利用 ES6 的数组解构赋值，在一行内完成指针的交换和移动，代码非常简洁。
functionreverseList(head){letprev=null;letcurr=head;while(curr!==null){[curr.next,prev,curr]=[prev,curr,curr.next];}returnprev;}- 时间复杂度：O(n)
- 空间复杂度：O(1)
- 优势：写法新颖，代码简短，适合展示对 ES6 语法的熟悉程度，但可读性略低于传统双指针
解法四：头插法
思路：新建一个空链表newHead，遍历原链表，每遇到一个节点就把它"头插"到新链表中。遍历结束后，newHead就是反转后链表的头节点。
functionreverseList(head){letnewHead=null;letcurr=head;while(curr!==null){constnext=curr.next;// 头插法：将当前节点插入到新链表的头部curr.next=newHead;newHead=curr;curr=next;}returnnewHead;}- 时间复杂度：O(n)
- 空间复杂度：O(1)
- 优势：思路直观，"头插法"是链表操作中的经典技巧，也适用于其他链表题目
四种解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 推荐指数 | 适用场景 |
|---|---|---|---|---|
| 双指针迭代 | O(n) | O(1) | ⭐⭐⭐⭐⭐ | 面试首选，最稳妥 |
| 递归 | O(n) | O(n) | ⭐⭐⭐⭐ | 代码简洁，但注意栈溢出 |
| 解构赋值 | O(n) | O(1) | ⭐⭐⭐ | ES6 语法糖，展示语言特性 |
| 头插法 | O(n) | O(1) | ⭐⭐⭐⭐ | 思路直观，头插技巧通用 |
扩展题
- 反转链表 II：给你单链表的头指针
head和两个整数left和right，反转从位置left到位置right的链表节点，返回反转后的链表。 - K 个一组翻转链表：给你链表的头节点
head，每k个节点一组进行翻转，返回修改后的链表。 - 两两交换链表中的节点：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
- 回文链表：给你一个单链表的头节点
head，请你判断该链表是否为回文链表。
