题目:

Reverse a singly linked list.

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

分析:

以下是Iterative方式的代码

class Solution {
    public ListNode reverseList(ListNode root) {
        if(root == null) return null;
        
        ListNode prev = null, curr = root;
        while(curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

以下是Recursive方式的代码

class Solution {
    public ListNode reverseList(ListNode root) {
        if(root == null || root.next == null) return root;
        
        ListNode next = root.next;
        ListNode ret = reverseList(root.next);
        next.next = root;
        root.next = null;
        // Always only return the tail of the whole list
        return ret;
    }
}