Friedrich Ewald My Personal Website

Leetcode: Partition List

Partition a linked list given a value x as a pivot element so that all nodes that are smaller than x come before all nodes that are greater or equal than x. The original order of the elements should be retained. This can be solved by creating two sub lists with empty nodes, called left and right and then concatenating those lists in the last step. The easiest way to achieve this is to create two new empty nodes and then, return left.next. This avoids having to keep track of None inside the loop and simpliefies the code.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
  def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
    if head is None or head.next is None:
      return head

    left_head = ListNode()
    right_head = ListNode()
    left_curr = left_head
    right_curr = right_head

    curr = head
    while curr is not None:
      if curr.val < x:
        left_curr.next = curr
        left_curr = left_curr.next
      else:
        right_curr.next = curr
        right_curr = right_curr.next
      curr = curr.next
    left_curr.next = right_head.next
    right_curr.next = None
    return left_head.next


About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.