Python solution utilizing dummy head node - O(n)


  • 0
    G
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        # @param {ListNode} head
        # @param {integer} x
        # @return {ListNode}
        def partition(self, head, x):
            if not head:
                return None
    
            less, greaterEqual = ListNode(0), ListNode(0)
            tempLess, tempGreaterEqual, temp = less, greaterEqual, head
            while temp:
                if temp.val < x:
                    tempLess.next = temp
                    tempLess = tempLess.next
                else:
                    tempGreaterEqual.next = temp
                    tempGreaterEqual = tempGreaterEqual.next
    
                cur = temp
                temp = temp.next
                cur.next = None
    
            tempLess.next = greaterEqual.next
            return less.next

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.