Concise solution in C++ (iterative and recursive)


  • 1
    K

    I know it's easy problem but we need to deal with it seriously, it's common in interviews and test our ability of pointer manipulation. both get passed in 8ms, the iterative solution is trivial:

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

    this is a more concise and understandable recursive version. executed from tail to top. and we return the pointer to the last node all the way when all the recursions are over.

    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            if (head == NULL || head->next == NULL) return head;   // case proof and recursion exit conditon
            ListNode *np = reverseList(head->next);
            head->next->next = head;         // make the next node point back to the node itself
            head->next = NULL;               // destroy the former pointer
            return np;
        }
    };

  • 0
    O

    I don't understand the code for destroy the former pointer, of course remove that line the program will go wrong, but I don't know why.


  • 0
    P

    if you don't do it you will create a loop. Head points to next element and next element points to head.


Log in to reply
 

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