Leetcode86. partition list (kotlin)

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

Partition List - LeetCode

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]

 

Approach

해당 문제는 주어진 x 보다 작은 것들은 왼쪽 더 큰것들은 오른쪽으로 정렬 하는 문제입니다.

여기서 주의해야 할점은 기존의 순서를 그대로 유지해야 합니다.

 

• x 보다 작은것들을 연결할 Listnode(lessNode) 를 만들고 x 보다 큰 것들을 연결할 LIstnode(moreNode) 를 만듭니다.
• head 를 iteration 하면서 x 보다 작으면 lessNode 의 next 로 Listnode(val) 을 추가하고 크다면 moreNode 의 next 로 Listnode(val) 을 추가합니다.

fun partition(head: ListNode, x: Int): ListNode? {
    val lessHead = ListNode(-1)
    val moreHead = ListNode(-1)
    var less = lessHead
    var more = moreHead
    var node: ListNode? = head
    while (node != null) {
        if (node.`val` < x) {
            less.next = ListNode(node.`val`)
            less = less.next!!
        } else {
            more.next = ListNode(node.`val`)
            more = more.next!!
        }
        node = node.next
    }

    less.next = moreHead.next

    return lessHead.next
}