206. Reverse Linked List.md

Solution1 (iterative)

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null, cur = head, next = head;
        while (next.next != null) {
            next = next.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        next.next = pre;
        return next;
    }
}

note

• time O(n), space O(1)
• The idea is to have three pointer: pre, cur and next to traverse through the original list and reverse nodes. After the loop, set next to point to pre.
• Remember to return next instead of head

Solution2 (recursion)

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode root = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return root;
    }
}