Clear C Solution


  • 0
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
     
    struct ListNode* getMid(struct ListNode*);
    struct ListNode* reverseList(struct ListNode*);
    void merge(struct ListNode*, struct ListNode*);
    
    void reorderList(struct ListNode* head) {
        if(head == NULL || head->next == NULL || head->next->next == NULL) return;
        
        struct ListNode* mid = getMid(head);
        struct ListNode* secondHalf = mid->next;
        mid->next = NULL;
        secondHalf = reverseList(secondHalf);
        merge(head, secondHalf);
        
    }
    
    struct ListNode* getMid(struct ListNode* head){
        struct ListNode* fast = head;
        struct ListNode* slow = head;
        while(fast->next!=NULL && fast->next->next!=NULL){
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
    
    struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode* tail = NULL;
        while(head!=NULL){
            struct ListNode* cur = head;
            head = head->next;
            
            cur->next = tail;
            tail = cur;
        }
        
        return tail;
    }
    
    void merge(struct ListNode* head1, struct ListNode* head2){
        struct ListNode* head = head1;
        
        while(head2!=NULL){
            struct ListNode* next = head2->next;
            head2->next = head->next;
            head->next = head2;
            
            head = head->next->next;
            head2 = next;
        }
    }
    

Log in to reply
 

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