[LeetCode] 86. Partition List - 노드(Node) + 구현(Implementation) JAVA

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

코드설명

노드(Node) + 구현(Implementation)를 활용합니다.

 

기본 구현은, 아래 예제와 함께 살펴보겠습니다.

1 -> 4 -> 3 -> 2 ->  5 -> 2  가 존재합니다.

lt Node -> 1 -> 2 -> 2

gte Node -> 4 -> 3 -> 5

로 만든뒤, lt Node의 마지막이 gte Node의 시작값을 바라보도록하면 됩니다.

 

코드

정답코드2입니다.

정답코드1과 다르게 dummy.next 대신에 lt.next 를 반환함으로써, lt가 빈 경우는 고려하지 않게되어 코드가 더 간단해졌습니다. (해당 부분 때문에, 처음에 틀렷었습니다.) 

/**
 * 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) {
        if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-999);
        ListNode lt = new ListNode(-999);
        ListNode gte = new ListNode(-999);  
 
        ListNode ltCur = lt;
        ListNode gteCur = gte;
        ListNode cur = head;
        while(cur != null){
            if(cur.val < x){
                ltCur.next = cur;
                ltCur = ltCur.next;
            } else if(cur.val >= x){
                gteCur.next = cur;
                gteCur = gteCur.next;
            }
            cur = cur.next;
        }
 
        ltCur.next = gte.next;
        gteCur.next = null;
        return lt.next;
    }
}

 

처음 제출한 정답코드1입니다.

정답은 맞지만, 불필요한 조건문으로 코드가 상대적으로 복잡합니다.

/**
 * 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) {
        if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-999);
        ListNode lt = new ListNode(-999);
        ListNode gte = new ListNode(-999);  
 
        ListNode ltCur = lt;
        ListNode gteCur = gte;
        ListNode cur = head;
        while(cur != null){
 
            if(cur.val < x){
                ltCur.next = cur;
                ltCur = ltCur.next;
            } else if(cur.val >= x){
                gteCur.next = cur;
                gteCur = gteCur.next;
            }
            cur = cur.next;
        }
 
        ltCur.next = null;
        gteCur.next = null;
 
        if(ltCur.val == -999){
            dummy.next = gte.next;
            return dummy.next;
        }
        dummy.next = lt.next;
        ltCur.next = gte.next;
        return dummy.next;
    }
}