LC206 reverse a linked list

Recursive

Reversing a linked list is reverse the head to point to previous, and recursively reverse the remaining again until the current’s node’s next is null.

/**
 * 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 == NULL)
            return head;
        return reverseRecur(head, NULL);
    }

    ListNode* reverseRecur(ListNode* head, ListNode* prev){
        if(head -> next == NULL){
            head -> next = prev;
            return head;
        }
        else{
            ListNode* retHead = reverseRecur(head -> next, head);
            head -> next = prev;
            return retHead;
        }
    }
};

Iterative

Iterative will turn back pointer one at a time.

    ListNode* reverseList(ListNode* head) {
        ListNode* prev = NULL;
        ListNode* tempNext = NULL;
        while(head != NULL){
            tempNext = head -> next;
            head -> next = prev;
            prev = head;
            head = tempNext;
        }
        return prev;
    }

In each iteration, if we are not on the null pointer, we will reverse it to point to the previous pointer.
After reversing the last node, we will also progress header by 1. So the actually head becomes the prev.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax