ReverseLinkedListOPT2 [source code]

public class ReverseLinkedListOPT2 {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null)
            return head;
        ListNode nextNode = head.next;
        ListNode newHead = reverseList(nextNode);
        nextNode.next = head;
        head.next = null;
        return newHead;
    }
}

这个是 discussion 上面给的一个 recursive 解, 非常聪明和干净利落. 我没有想到的一点是, 在 recurse 之前, 保存好head.next, 这样在 recurse 完了之后就不用还专门扫一遍去找这个点了, which should be the new parent for head. 这个优化直接把速度从 quadratic 降到了 linear;

1ms 的速度, 还是很不错的;

这个是 editorial 上面给出第一个类似的思路:

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;  
}

可以看到就算不专门用一个 buffer 保存head.next, 我们还是可以有办法 access 到的; 只能怪我自己对于指针的理解还不够深入, 没有办法瞬间想到这个解;

/**

• Definition for singly-linked list.
• public class ListNode {
• int val;
• ListNode next;
• ListNode(int x) { val = x; }
• }
  */

Problem Description

Reverse a singly linked list.

click to show more hints.

Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?

Difficulty:Easy
Category:Algorithms
Acceptance:45.04%
Contributor: LeetCode
Companies
uber facebook twitter zenefits amazon microsoft snapchat apple yahoo bloomberg yelp adobe
Related Topics
linked list
Similar Questions
Reverse Linked List II Binary Tree Upside Down Palindrome Linked List