leetcode刷题笔记-Reverse Linked List

自己的想法

  1. 遍历Linked List,通过list的add.(index,val)方法,将数据放入list。
  2. 然后,遍历list封装Linked。
    bingo代码实现

    运行结果

    1
    Runtime: 3 ms, faster than 2.86% of Java online submissions for Reverse Linked List.

结果分析: 弱爆了

参考官方解决方法

迭代法[Accepted]

  1. 蹩脚的翻译思路解析

    已有链表 1->2->3->null
    当你遍历里列表时,将当前节点的下一个指针,指向前一个元素。

    理解:比如当前节点是11的下一个指针指向的是2,前一个元素是null,经过这个操作后,当前节点就变成了1->null

    因为节点没有指向前一个节点的引用,所以需要预先准备一个来存储它。
    在更改引用之前,你还需要另一个指针来存储下一个节点。最后返回新的引用
    示例代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public ListNode reverseList(ListNode head) {
    ListNode prev = null; // step 1
    ListNode curr = head; // step 2
    while (curr != null) {// step 3
    ListNode nextTemp = curr.next;// step 4
    curr.next = prev; // step 5
    prev = curr;// step 6
    curr = nextTemp; //step 7
    }
    return prev;
    }

    代码执行解析:

    已知条件 head = 1->2->3->null

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    * while第一次执行:
    * head = 1,2,3
    * step 1 prev = null
    * step 2 prev = null; curr = 1,2,3
    * step 3 prev = null; curr = 1,2,3
    * step 4 prev = null; curr = 1,2,3; nextTemp = 2,3
    * step 5 prev = null; curr = 1; nextTemp = 2,3
    * step 6 prev = 1; curr = 1; nextTemp = 2,3
    * step 7 prev = 1; curr = 2,3;
    * while第二次执行:
    * step 4 prev = 1; curr = 2,3;nextTemp =3
    * step 5 prev = 1; curr = 2,1;nextTemp =3
    * step 6 prev = 2,1;curr = 2,1;nextTemp =3
    * step 7 prev = 2,1;curr = 3;
    * while第三次执行:
    * step 4 prev = 2,1;curr = 3;nextTemp =null
    * step 5 prev = 2,1;curr = 3,2,1;nextTemp=null
    * step 6 prev = 3,2,1;curr=3,2,1;nextTemp=null;
    * step 7 prev = 3,2,1;curr=null
    * 跳出循环
    * return prev

递归[Accepted]

  1. 蹩脚的翻译思路解析

    递归的版本稍微有些复杂,解题的关键是反向。假设剩余的列表已经被反转,前面的部分如何解决呢?假设list是:

    假设节点nk+1 到 n m 已经被反转了,当前循环处在nk节点。

    我们想要nk+1‘s 的下一个节点是nk

    所以nk.next.next = nk

    对于第一个节点,要注意的是它的下一个节点指向Ø。如果忘记这个,那么你会得倒一个循环链表,如果使用长度2的链表集合测试代码,那么复现这个bug。

    1
    2
    3
    4
    5
    6
    7
    public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
    }

    代码执行解析:对于这个方法,笔者有些疑惑,等找到答案后,再来完善。

    翻阅讨论区的时候,我找到了一个更容易理解的方案。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public  ListNode reverseList4(ListNode head) {
    return reverseListInt(head, null);
    }
    private ListNode reverseListInt(ListNode head, ListNode newHead) {
    if (head == null) {
    return newHead;
    }
    ListNode next = head.next;
    head.next = newHead;
    return reverseListInt(next, head);
    }

    总结:

    以我个人的能力而言,理解这个问题,并能找出自己的解决方案。但是没有最优解的能力,参考了官方提供的例子和讨论区的答案,增加了见识。代码实现能力未增加,但是见识、意识有所长进。也许进步就需要这样积累吧。

留言

⬆︎TOP