Reverse Linked List

, , , , ,

Question

Reverse a singly linked list.

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

Example

1
2
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Solution

the following code explains.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// iteratively.
// time:O(n) space:O(1)
public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = next;
        }
        return newHead;
    }

// recursion
//time:O(n) space:O(n)
public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }