CTCI | 분할(Partition)

값 x가 주어졌을 때 x보다 작은 노드들을 앞에, 크거나 같은 노드들을 뒤에 오게하는 코드를 작성하라

Linked List에서 약간의 Sorting을 해야하는 문제다. 복잡해 보이지만, 생각보다 단순하다. LinkedList 두개를 생성해서, x보다 작은것은 첫번째 리스트에, 큰것은 두번째 리스트에 추가하고, 나중에 그 두 리스트를 연결만 하면 된다. 여기서, 난이도가 쉬운 이유는, 오른쪽 노드 조합에서 x가 꼭 앞에 오지 않아도 되기도 하고, 각각의 Linked List가 Sorting되지 않아도 되기 때문이다.

 

그림으로 한번 나타내보자.

 

작은 숫자들 리스트의 첫 노드가 될 dummy node와 큰 노드들의 리스트를 만들 dummy node를 만들어서, 해당하는 숫자를 그 뒤에 쭉 붙인 후, 원래 linked list의 맨 끝까지 도달했다면, 이제 두 리스트를 연결해주면 된다. 이때, 주의할점이 있다. 작은 노드의 current point가 큰 노드 리스트의 dummy node의 next를 포인트 하도록 해주어서 small 리스트와 long 리스트를 연결해줌과 동시에, 큰값만 있는 리스트의 맨 마지막 노드의 next를 null로 해주어야한다. 이 이유는, 위 예시같이, 6을 갖고있는 노드를 보면, 원래는 2를 포인트 하고 있다. 하지만 2는 이미 small node list에 더해졌고, 2의 다음은 7, 즉 큰 노드 리스트의 첫번째 노드로 설정이 되어서 cycle이 생겨버리는 에러가 나기 때문이다. 자, 그럼 이 사항을 생각하면서 코딩해보자.

Node reorderList(Node head, int k){

	// 큰노드, 작은노드의 첫번째 더미 노드를 생성한다.
    Node sDummy = new Node(-1);
    Node bDummy = new Node(-1);
    
    // while loop을 여행할 curr 노드 포인터를 head부터 시작하도록 한다.
    Node curr = head;
    
    // 상황에 맞게 각 노드를 더해줄 수 있도록, 작은/큰노드 그룹의 더미노드를 포인트한다.
    Node sCurr = sDummy;
    Node bCurr = bDummy;
    
    while(curr != null){
    	if(curr.val < k){
        	sCurr.next = curr;
            sCurr = sCurr.next;
        } else {
        	bCurr.next = curr;
            bCurr = bCurr.next;
        }
        
        curr = curr.next;
    }
    
    // 작은 노드 리스트의 끝과 큰 노드 리스트의 시작을 연결
    sCurr.next = bDummy.next;
    // 큰 노드 리스트의 끝을 null로 설정
    bCurr.next = null;
    
    return sDummy.next;
}

 

Time complexity는 리스트를 한 번 순회하므로 O(N)이고, 여기서 N은 리스트의 노드 수이다다. Space complexity는 추가적인 공간을 사용하지 않고, 입력으로 주어진 리스트의 노드를 재배치만 하기 때문에 O(1)이다.

 

 

 

Reference

https://github.com/careercup/CtCI-6th-Edition/tree/master/Java/Ch%2002.%20Linked%20Lists/Q2_04_Partition

CtCI-6th-Edition/Java/Ch 02. Linked Lists/Q2_04_Partition at master · careercup/CtCI-6th-Edition