C++ solution.. 78ms


  • 1
    H
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        void reorderList(ListNode *head) {
     	ListNode *mid = head , *midfast = head , *current =  head;
    
    	if(head == NULL || head->next == NULL)
    		return ;
    
    	//midfast = head->next;
    
    	// calculate the  middle elem
    	while(midfast != NULL && midfast->next != NULL ){
    		mid = mid->next;
    		midfast = midfast->next->next;
    	}
    
    	ListNode *prevmid = mid;
    	mid = mid->next;
    	if(mid == NULL)
    	    return;
    
    	// reverse and partition the list
    	ListNode *prev = NULL , *newNode = NULL;
    	if(mid->next == NULL)
    		prev = mid;
        else{
    	while(mid != NULL ){
    		newNode = mid->next;
    		mid->next = prev;
    		prev = mid;
    		mid = newNode;
    	}
            
        }
    	
    
    	// partitioning the lists
    	prevmid->next = NULL;
    	//prev has the head pointer of the second list
    	ListNode *newcur = NULL , *newMid = NULL;
    	while(current != NULL && prev != NULL){
    		newcur = current->next;
    		current->next = prev;
    		current = newcur;
    		newMid = prev->next;
    		prev->next = current;
    		prev = newMid;
    	}
    	return;
    }
    };
    

    the above approach I used is to divide the list into two parts. But in this code I dont like is taking too mainy pointers to save the reference of next nodes. Can someone suggest me a better approach?

    Thanks


Log in to reply
 

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