15.08.2023
86. Partition List medium
blog post
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
tonull
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
}