206 Reverse Linked List

Reverse a singly linked list.

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

iterative solution

/**
 * 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 or head->next == NULL ) return head;
        ListNode* p1 = head, *p2 = head->next;
        while ( true ) {
            ListNode *tmpp = p2->next;
            p2->next = p1;
            p1 = p2;
            p2 = tmpp;
            if ( p2 == NULL ) break;
        }
        head->next = NULL;
        return p1;
    }
};

Note
Always remember to terminate the linked list appropriately.

head->next = NULL

iterative solution

class Solution {
public:
    vector<ListNode*> reverseHelp(ListNode* head) {
        // return (head, tail)
        vector<ListNode*> res(2, head);
        if ( head->next == NULL ) return res;
        res = reverseHelp(head->next);
        res[1]->next = head;
        res[1] = head;
        // TERMINATE THE LINKED LIST!
        res[1]->next = NULL;
        return res;
    }
    ListNode* reverseList(ListNode* head) {
        if ( head == NULL ) return head;
        return reverseHelp(head)[0];
    }
};