ReverseLinkedListOPT3 [source code]

public class ReverseLinkedListOPT3 {
    public ListNode reverseList(ListNode head) {
        /* recursive solution */
        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);
    }
}

这个是 discussion 上给的另外一个 recursive 的最优解; 这个的思路也很好理解, 其实比较类似 ocaml 上面的思路, 用两个参数来表示两个 list, 然后把左边的一个一个的从head 位置拿下来, 接到第二个 list 的 head 上. 这个就是我们 prolog 或者 ocaml 的时候常用的 reverse 的思路, 他这里用上了;

这个算法也暗示很多语言之间共通性其实很多;

这个的速度也是1ms;

/**

• 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