【LeetCode】反转链表

欢迎来到李耶的频道【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){letprevnull;letcurrhead;while(curr!null){constnextcurr.next;// 保存下一个节点curr.nextprev;// 反转指针prevcurr;// prev 后移currnext;// curr 后移}returnprev;}时间复杂度O(n)遍历一次链表空间复杂度O(1)只使用了常数个指针变量优势最实用性能最优面试中最稳妥的写法解法二递归思路递归的核心思想是假设head.next之后的链表已经被反转好了然后只需要处理head和head.next之间的指针关系。递归的终止条件是链表为空或只有一个节点。functionreverseList(head){// 递归终止条件空链表或只有一个节点if(headnull||head.nextnull){returnhead;}// 递归反转 head.next 之后的链表返回新的头节点constnewHeadreverseList(head.next);// 让 head.next 指向 head完成反转head.next.nexthead;head.nextnull;returnnewHead;}时间复杂度O(n)每个节点访问一次空间复杂度O(n)递归调用栈的深度取决于链表长度优势代码最简洁体现了递归的优雅但要注意链表过长可能导致栈溢出解法三解构赋值ES6 语法糖思路本质上还是双指针法但利用 ES6 的数组解构赋值在一行内完成指针的交换和移动代码非常简洁。functionreverseList(head){letprevnull;letcurrhead;while(curr!null){[curr.next,prev,curr][prev,curr,curr.next];}returnprev;}时间复杂度O(n)空间复杂度O(1)优势写法新颖代码简短适合展示对 ES6 语法的熟悉程度但可读性略低于传统双指针解法四头插法思路新建一个空链表newHead遍历原链表每遇到一个节点就把它头插到新链表中。遍历结束后newHead就是反转后链表的头节点。functionreverseList(head){letnewHeadnull;letcurrhead;while(curr!null){constnextcurr.next;// 头插法将当前节点插入到新链表的头部curr.nextnewHead;newHeadcurr;currnext;}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请你判断该链表是否为回文链表。