ReverseLinkedList [source code]

public class ReverseLinkedList {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode nextList = reverseList(head.next);
        ListNode end = nextList;
        while (end.next != null) end = end.next;
        end.next = head;
        head.next = null;
        return nextList;
    }
}

居然很奇怪的一次就过了, 但是速度垫底, 30ms, 1%.
应该还是有更好的解法的;

虽然如此, 如果让你写一个直接的 recursive 的解法, 还是要会写的, 思路基本就是, 假如你有 head.next 开头的这个 list 已经被 reverse 了, 你怎么把 head 放进去? 注意 basecase 的处理;

/**

• 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