Problem description:

Reverse a singly linked list.

Example:

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

Follow up:

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

Solution iterative better:

Use two variables, pre and cur. Another local variable to keep the swapping node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre= NULL, *cur= head;
        
        while(cur){
            ListNode* tmp= cur->next;
            cur->next= pre;
            pre= cur;
            cur= tmp;
        }
        return pre;
    }
};

Solution:

Iteratively solution:
Create a dummy node in front of the head node. Use pre and cur to do the swap. But when we do the swapping, we need to use a tmp node to store the cur to avoid dropping nodes in between.

1
2
3
4
dummy-A-B-C-D-E-F
        
dummy-E-D-C-B-A-F
dummy-F-E-D-C-B-A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* dummy= new ListNode(0);
        dummy->next= head;
        ListNode *pre= dummy, *cur= head;
        while(cur && cur->next){
            ListNode* tmp= pre->next;
            pre->next= cur->next;
            cur->next= cur->next->next;
            pre->next->next= tmp;
        }
        return dummy->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode();
        
        while(head != null){
            ListNode tmp = head.next;
            head.next = dummy.next;
            dummy.next = head;
            head = tmp;
        }
        
        return dummy.next;
        
    }
}

time complexity: $O(n))$
space complexity: $O(1)$

Recursive solution:
Try to think the end state for recursion. When the recursion reaches to 5, it would return node 5 to previous recursion. And previous recursion stack would look like this.

1
4->5->null

And what we want is to reverse the list, so we could put 4 to the back of 5.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !(head -> next)) {
            return head;
        }
        ListNode* node = reverseList(head -> next);
        head -> next -> next = head;
        head -> next = NULL;
        return node;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        
        ListNode node = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }
}

reference:
https://goo.gl/HSqym3