.leetcode(86. Partition List)

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

 

1. 2022.02.06 시도

소요시간: 22분

class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return null;
        }
        
        ListNode start = new ListNode(200);
        start.next = head;
        ListNode prev = start;
        ListNode ret = start;
        ListNode current = head;
        while(current != null) {
            if (current.val < x && start.next == current) {
                start = current;
                prev = current;
                current = current.next;
            } else if (current.val < x && start.next != current) {
                ListNode temp = current.next;
                current.next = start.next;
                start.next = current;
                current = temp;
                prev.next = current;
                start = start.next;
            } else {
                prev = prev.next;
                current = current.next;
            }
        }
        
        return ret.next;
    }
}

풀이 접근 과정

일단은 current 포인터가 필요하다. 하나가 진행하면서 앞으로 나아가야하니 말이다.

두번재로는 start포인터라는 작은 숫자들의 마지막을 가리키는 포인터가 필요하다.

세번째로는 current노드가 앞으로 이동했을 때, 이전 노드에서 다음 노드를 가리킬 때에 대해서도 수정이 필요하여 prev포인터가 필요하다.

마지막으로 결과값을 노출하기위해 ret포인터를 기억해둔다.

처음출발할 때 start포인터가 꼬이는게 있어서 start.next == current로 상황을 정리했다.

 

느낀점

• start.next == current 부분이 제일 오래걸렸다. 쉽게 상황이 풀릴줄알고 만만하게 봤는데 이 부분 고치는데 시간을 많이 썼다.
• 솔루션은 기가막히게 풀었다. 감탄했다. 2가지를 꼬매는 듯한 기법으로 풀이를 했는데 배울만하여 적어본다.

class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return null;
        }
 
        ListNode beforeHead = new ListNode();
        ListNode before = beforeHead;
        ListNode afterHead = new ListNode();
        ListNode after = afterHead;
        
        while(head != null) {
            if (head.val < x) {
                before.next = head;
                before = before.next;
            } else {
                after.next = head;
                after = after.next;
            }
            head = head.next;
        }
        after.next = null;
        before.next = afterHead.next;
        
        
        return beforeHead.next;
    }
}

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형