反转链表

曾经终败给现在 2022-12-27 01:21 316阅读 0赞

剑指Offer 24 反转链表 [easy]
在这里插入图片描述

题解1

  1. 思路：栈
  2. 时间复杂度：O(n) O(2 * n) 入栈 + 出栈
  3. 空间复杂度：O(n) 栈空间

  4. 实现

    1. /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    2. /** * @param {ListNode} head * @return {ListNode} */
    3. var reverseList = function(head) { 
    4.     // 预处理
    5.     if(!head) return head;
    7.     let stack = [head];
    8.     let curr = head;
    9.     while(curr.next){ 
    10.         stack.push(curr = curr.next);
    11.     }
    12.     let result = stack.pop();
    13.     while(curr.next = stack.pop() || null) curr = curr.next;
    14.     return result;
    15. };

题解2

  1. 思路：双引用(指针)法 pre, curr
  2. 时间复杂度：O(n)
  3. 空间复杂度：O(1) 指针空间

  4. 实现

    1. /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    2. /** * @param {ListNode} head * @return {ListNode} */
    3. var reverseList = function(head) { 
    4.     // 预处理
    5.     if(!head) return head;
    7.     // 双引用法
    8.     let pre = head;
    9.     let curr = pre.next;
    10.     pre.next = null;    // 反转链表尾指向null
    11.     while(curr){ 
    12.         let temp = curr;
    13.         curr = curr.next;
    14.         temp.next = pre;
    15.         pre = temp;
    16.     }
    17.     return pre;
    18. };

发表评论

表情：
评论列表 （有 0 条评论，316人围观）

还没有评论，来说两句吧...

相关阅读

    相关 反转链表

    题目 给定一个常数K以及一个单链表L，请编写程序将L中每K个结点反转。例如：给定L为1→2→3→4→5→6，K为3，则输出应该为3→2→1→6→5→4；如果K为4，则输出

    た 入场券た 入场券/ 0 赞/ 341 阅读

    相关 反转链表

    时间限制：1秒 空间限制：32768K 热度指数：408664 本题知识点： 链表 算法知识视频讲解 题目描述 输入一个链表，反转链表后，输出新链表的表头。

    妖狐艹你老母妖狐艹你老母/ 0 赞/ 375 阅读