[LeetCode] #86 partition List (repeat : 0 )

두시간이나 걸린 문제 ..  x보다 작으면 앞에다가 옮기고, x보다 크면 뒤에다가 옮기는 문제다. 노드의 순서는 그대로 유지한 상태여야한다. dummy 노드 두개를 만들어서 x보다 작으면 dummy1에다 넣고 , x보다 크면 dummy2에다 넣은 후 둘이 합치면 된다. 

 

 

#Description 

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

 

Example 1:

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

Example 2:

Input: head = [2,1], x = 2
Output: [1,2]

#Solution 

class Solution {
    public ListNode partition(ListNode head, int x) {
        //initialize two list nodes as placeholders 
        //this helps to simplify the manipuation of lists
        ListNode dummy1 = new ListNode(0);
        ListNode dummy2 = new ListNode(0);
        
        //initialize two pointers to the first node of two lists 
        ListNode prev1 = dummy1;
        ListNode prev2 = dummy2;
        
        //initialize current list to point the original list
        //this pointer will track of the node of the list 
        ListNode current = head;
        
        //iterates till the end of the list 
        while(current != null){
        	//compare value of node with x 
            if(current.val < x){ //if the value is smaller than x 
                prev1.next = current; // link the current node to the end of the dummy1 list
                prev1 = prev1.next;//move to the next node
            }else{ //if the value is greater or equal to x 
                prev2.next = current; //link the current node to the end of the dummy2 list
                prev2 = prev2.next; //move to the next node
            }
            current = current.next;
        }
        
        prev2.next = null; // terminate the second list, this prevents cycles in the list
        
        //connect two lists 
        //the first list is followed by the second list 
        prev1.next = dummy2.next;
        
        //upate the head of the original list
        //the head points to the start of the first list 
        head = dummy1.next;
        
        return head;
        
    }
}

 

In terms of space complexity, it is O(1) constant space. because this algorithm uses only constant numbers of nodes(prev1,2,dummy1,2,current)

In terms of time complexity. It is o(n) linear running time. the n represents number of nodes in the linked list  

 

 

 

 

 

 

 

https://leetcode.com/problems/partition-list/submissions/

LeetCode - The World's Leading Online Programming Learning Platform