206. Reverse Linked List - cocoder39/coco39_LC GitHub Wiki

206. Reverse Linked List

algorithm 1

ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* nxt = head;
        while (nxt) {
            ListNode* cur = nxt;
            nxt = nxt->next;
            cur->next = pre;
            pre = cur;
        }
        return pre;
    }

algorithm 2: same way as reverse linked list ii

ListNode* reverseList(ListNode* head) {
        ListNode dummy(0);
        dummy.next = head;
        
        ListNode* tail = head;
        while (tail && tail->next) {
            ListNode* cur = tail->next;
            tail->next = cur->next;
            cur->next = dummy.next;
            dummy.next = cur;
        }
        return dummy.next;
    }

iterative

ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        
        ListNode* second = head->next;
        ListNode* h = reverseList(second);
        second->next = head;
        head->next = nullptr;
        return h;
    }

divide-and-conquer: t(n) = 2t(n/2) + O(n/2) < 2t(n/2) + O(n) = O(n log n)

ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        
        ListNode dummy(0);
        dummy.next = head;
        ListNode *slow = &dummy, *fast = &dummy;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        ListNode* h1 = slow->next;
        slow->next = nullptr;
        ListNode* h2 = reverseList(head);
        ListNode* h3 = reverseList(h1);
        h1->next = h2;
        return h3;
    }