LeetCode Entry

86. Partition List

15.08.2023 medium 2023 kotlin

Partition a Linked List by x value

86. Partition List medium blog post substack

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/309

Problem TLDR

Partition a Linked List by x value

Intuition

Keep two nodes for less and for more than x, and add to them, iterating over the list. Finally, concatenate more to less.

Approach

• To avoid cycles, make sure to set each next to null
• Use dummy head technique

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(1)\)

Code

    fun partition(head: ListNode?, x: Int): ListNode? {
        val dummyLess = ListNode(0)
        val dummyMore = ListNode(0)
        var curr = head
        var less = dummyLess
        var more = dummyMore
        while (curr != null) {
          if (curr.`val` < x) {
            less.next = curr
            less = curr
          } else {
            more.next = curr
            more = curr
          }
          val next = curr.next
          curr.next = null
          curr = next
        }
        less.next = dummyMore.next
        return dummyLess.next
    }