86.-partition-list.md

86. Partition List

• Medium

• 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]
  

Analysis

The idea is to create two lists that contains those come after the x and those that comes before the x. Some of the ideas are explained in the comments.

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        h1=l1=ListNode(0)
        h2=l2=ListNode(0)
        while head:
            if head.val<x:
                #if the value is lower than the target x, we link it to the first list 
                l1.next=head
                l1=l1.next
            else:
                #if it is greater or equal to x, link it to the second list 
                l2.next=head
                l2=l2.next
            head=head.next
            
        #we need to cut the second list or there might be a cycle in the list we create
        l2.next=None
        
        #we then link the second link to the end of the first link
        l1.next=h2.next
        return h1.next