8ms C++ Iterative and Recursive Solutions with Explanations


  • 71

    xWell, since the head pointer may also be modified, we create a new_head that points to it to facilitate the reverse process.

    For the example list 1 -> 2 -> 3 -> 4 -> 5 in the problem statement, it will become 0 -> 1 -> 2 -> 3 -> 4 -> 5 (we init new_head -> val to be 0). Then we set a pointer pre to new_head and another cur to head. Then we keep inserting cur -> next after pre until cur becomes the last node. The code is follows.

    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            ListNode* new_head = new ListNode(0);
            new_head -> next = head;
            ListNode* pre = new_head;
            ListNode* cur = head; 
            while (cur && cur -> next) {
                ListNode* temp = pre -> next;
                pre -> next = cur -> next;
                cur -> next = cur -> next -> next; 
                pre -> next -> next = temp;
            }
            return new_head -> next;
        }
    };
    

    This link provides a more concise solution without using the new_head. The idea is to reverse one node at a time for the beginning of the list. The rewritten code is as follows.

    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            ListNode* pre = NULL;
            while (head) {
                ListNode* next = head -> next;
                head -> next = pre;
                pre = head;
                head = next;
            } 
            return pre;
        }
    };
    

    Well, both of the above solutions are iterative. The hint has also suggested us to use recursion. In fact, the above link has a nice recursive solution, whose rewritten code is as follows.

    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; 
        }
    }; 
    

    The basic idea of this recursive solution is to reverse all the following nodes after head. Then we need to set head to be the final node in the reversed list. We simply set its next node in the original list (head -> next) to point to it and sets its next to be NULL.


  • 31
    T

    Share my codes

    iterative

     ListNode* reverseList(ListNode* head) {
            ListNode *prev = NULL, *cur=head, *tmp;
            while(cur){
                tmp = cur->next;
                cur->next = prev;
                prev = cur;
                cur = tmp;
            }
            return prev;
       }
    

    recursive

    ListNode* reverseList(ListNode* head) {
        if(!head || !(head->next))  return head;
        auto res = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return res;
    }

  • 0

    Thanks for the nice iterative version :-)


  • 0
    X

    thanks for the decent recursive solution


  • 0
    S

    In the recursive solution, why is it wrong to use node -> next = head instead of head -> next -> next = head? Thanks a lot!


  • 2
    E

    @Shane
    before reverse:first->second->third.
    after reverse:second->first,
    head->next->next = head means second->first.


  • 0
    A

    thanks for sharing the recursive method. what is the time complexity of the recursive solution? seems that for each node, we need to reserve all the later nodes, therefore, it is n+(n-1) + ... + 1 so it is O(n^2) ?


  • 0
    S
    This post is deleted!

  • 0
    H

    Can someone explain head->next->next = head;?


  • 0
    S

    @evilcoder nice explain


  • 1
    S

    @hck94829 pls check evilcoder's explanation, and maybe do a [1,2,3] recursion and I think you will see it.

    the trick is that the "head" ptr already points to the second last node, so that head->n is the last one in each recursion, then (head->n)->n point back to the second last node (A.K.A head), then recursively, your head->n =NULL will keep updating till then end node reversely (which is the original head of the list).

    Man, I am not good at recursion, so I think the running time is O(n), since the code does depth first, then re-link the first<-second recursively. If I am wrong, any help is appropriated.

    Thx


  • 0
    J

    My solution is quite similar to @tamugaoqi while the initialization is different and takes the place of the first iteration, but it will cause "Time Limit Exceeded" for cases like [1,2]. I wonder why it will cause the problem. Thanks a lot.

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

  • 1
    J

    @jywu The problem is your reversed linked list is not null-terminated. You need to create a dummy node that points to the head. After you've finished reversing the linked list in the while loop, set the dummy node to null. This should solve your problem.


  • 0
    J

    @jagans94 Thanks a lot. This solves my problem.


  • 0
    M

    Regarding the recursive function, the first time it will actually return is when head->next is NULL. So how can we access head->next->next right after that? Will that not lead to segmentation fault?


  • 0
    Y

    @meadowt After it returns because of head -> next is NULL, the head would be the second last element. so head -> next -> next would set the last one element's next.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.