20ms simple C solution with comments


  • 2
    H
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    struct ListNode* revertList(struct ListNode* head) {
        if(head == NULL || head->next == NULL) {
            return head;
        }
        
        struct ListNode* prev = NULL;
        struct ListNode* cur = head;
        struct ListNode* next = NULL;
        
        while(cur != NULL) {
            next = cur->next;
            
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        
        return prev;
    }
     
    void reorderList(struct ListNode* head) {
        struct ListNode* newHead = NULL;
        struct ListNode* newNode = NULL;
        struct ListNode* node = head;
        
        if(head == NULL || head->next == NULL) {
            return;
        }
        
        //find the middle nodes
        struct ListNode* slow = head;
        struct ListNode* fast = head->next->next;
        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        if(fast != NULL) {
            slow = slow->next;
        }
        
        newHead = slow->next;
        slow->next = NULL;
        
        //revert the 2nd linklist
        newHead = revertList(newHead);
        
        //merge 2 link list together
        newNode = newHead;
        node = head;
        int index = 0;
        while(newNode != NULL && node != NULL) {
            if((index % 2) == 0) {
                struct ListNode* next = node->next;
                node->next = newNode;
                node = next;
            }
            else {
                struct ListNode* next = newNode->next;
                newNode->next = node;
                newNode = next;
            }
            index++;
        }
    }

Log in to reply
 

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