Linked List | Partition List

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.

주어진 Linked List를 파티션 하라는 문제이다. Integer 값이 주어지는데, 이보다 작으면 순서대로 왼쪽에, 크거나 같으면 순서대로 오른쪽에 나열해서 새로운 Linked List를 리턴하는 문제이다. Dummy Node를 이용해서 손쉽게 풀 수 있다.

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummyL = new ListNode(-1);
        ListNode dummyGE = new ListNode(-1);
        ListNode leftCurr = dummyL;
        ListNode rightCurr = dummyGE;
        
        while(head != null){
            if(head.val < x){
                leftCurr.next = head;
                leftCurr = leftCurr.next;
            } else {
                rightCurr.next = head;
                rightCurr = rightCurr.next;
            }
            head = head.next;
        }
        leftCurr.next = dummyGE.next;
        rightCurr.next = null;
        return dummyL.next;
    }
}

* Time Complexity: O(N)

* Space Complexity: O(1)

 

중간 과정에서 포인터만 변경하는 식으로 풀이했다. 작은값들이 모인 왼쪽 리스트의 head가 언제 등장할지 모르기때문에 dummyL을 만들어주고, 똑같이, 오른쪽 dummyGE를 만들어주었다. 그리고 앞으로 추가가 될 때 마다, tail을 가르킬 curr 포인터들도 생성했다. 룹 안에서, 만약 작은 값을 발견하면, 왼쪽 부분 리스트의 tail의 next을 현재 노드로, 반대로 같거나 큰값을 발견하면 오른쪽을 바꿔주고, 곧바로 방금 더해진 노드로 포인터를 옮긴다. 두 경우 모두, head에서 한칸씩 이동한다. While loop이 끝나면, 두 리스트를 이어주고, right list에 맨 마지막 노드의 next가 null이 되도록 설정하면, 깔끔한 리스트가 만들어진다.

위 풀이법으로 했을 때, 최상위(100%)의 속도를 내었고, Space 또한 상위 75.94%를 보였다.

 

 

자, 44렙이상 또는 번개 기술을 배운 피카츄는 오른쪽으로 정렬, 그 이외 수련중인 피카츄는 왼쪽으로 정렬합시다!

 

 

Reference

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

Partition List - LeetCode