Is there better way of solving this problem?


  • 0
    V

    I wanted to solve this problem by changing pointers and not by copying the node values. While working on this problem, I came across below scenarios.

    • left and right nodes are next to each other.
    • left and right nodes are far(some nodes between them)
    • General case is updating head pointer.

    left node is fixed at position i ( 1 to n-1) and it will be compared with next i+1 to n nodes using right pointer. If left node is greater than right node then adjust the pointers such that left node becomes right and right becomes left node.

    ListNode *insertionSortList(ListNode *head) {
    	if(head == nullptr)
    		return nullptr;
    	ListNode *left = head, *right = nullptr, *prevLeft = nullptr, *prevRight = nullptr;
    	bool firstNode = true;
    	while(left->next != nullptr) {
    		prevRight = nullptr;
    		right = left->next;
    		while(right != nullptr) {
    			if(left->val > right->val) {
    				ListNode *temp = left->next == right ? left : left->next;
    				left->next = right->next;
    				right->next = temp;
    
    				//swapping left and right to keep logic clear
    				temp = left; left = right; 	right = temp;
    
    				if(prevLeft)
    					prevLeft->next = left;
    				if(prevRight) 
    					prevRight->next = right;
    
    				if(firstNode)
    					head = left;
    			}
    			prevRight = right;
    			right = right->next;
    		}
    		prevLeft = left;
    		left = left->next;
    		firstNode = false;
    	}
    	return head;
    }

  • 0
    C
    This post is deleted!

  • 0
    S

    Thanks for your sharing, unfortunately such answer is against principle here. Please make a high quality post, read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 0
    V

    I made big mistake. The logic is more like bubble sort instead of insertion sort. Thanks cm3164 for pointing out.


Log in to reply
 

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