# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def partition(self, head, x): """ :type head: ListNode :type x: int :rtype: ListNode """ dummy1 = ListNode(0) dummy2 = ListNode(0) p1 = dummy1 p2 = dummy2 p = head while p: if p.val < x: p1.next = p p1 = p1.next p = p.next p1.next = None # If you are merging two lists, then you don't have to do that. # but if you are doing in one list, you have to do set None to the last node. # Otherwise, there will be a loop, `node1(p1)->node2(p2)`. else: p2.next = p p2 = p2.next p = p.next p2.next = None p1.next = dummy2.next return dummy1.next
Given 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.
1->4->3->2->5->2 and x = 3,