Leetcode 86: Partition List
Problem Statement:
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]Example 2:
Input: head = [2,1], x = 2
Output: [1,2]Solution:
Let’s say we forget that the question involves a linked list for a moment. How would one approach it?
What if we replace these nodes by people with different heights and we ask the same question. And the condition is to separate people whose heights are less than X cms and ones who are equal or taller than X cms.
One would go through each and every one, hand pick ’em and put them in two groups based on their heights.
The only thing missing here to suit our original problem is to link these two groups through a common thread. And that thread is the last person put into shorter group connected to the first person picked in the taller group.
Now, let’s convert this into code.
class Solution(object):
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
#before_list --> group of nodes < x
#after_list --> group of nodes >= x
#before_head --> head of before_list
#after_head --> head of after_list #Dummy intermediate nodes
before_list = ListNode(-2)
before_head = before_list
after_list = ListNode(-2)
after_head = after_list
current = head
while current:
if current.val < x:
before_head.next = current
before_head = before_head.next
else:
after_head.next = current
after_head = after_head.next
current = current.next
after_head.next = None
before_head.next = after_list.next
return before_list.next
I hope this helps anyone out there. Please let me know your thoughts in the comments. Thanks! :)
Edit
Please follow my github repository for interview preparation in the link below. Thanks!