Golang concise solution using 2 pointers


  • 0

    Just having a pointer for a runner to iterate the former half of the partition and another to iterate the latter half.
    Important note is, once the iteration is over, we need to set nil to the tail of two pointers to cut the existing connection.
    (otherwise you see an infinite loop in our result which results in TLE on some Leetcode test case)

    func partition(head *ListNode, x int) *ListNode {
    	first, second := &ListNode{}, &ListNode{}
    	dummyHeadFirst, dummyHeadSecond := first, second
    
    	for head != nil {
    		if head.Val < x {
    			first.Next = head
    			first = first.Next
    		} else {
    			second.Next = head
    			second = second.Next
    		}
    		head = head.Next
    	}
    	first.Next, second.Next = nil, nil // cut the connection
    	if dummyHeadSecond.Next != nil {
    		first.Next = dummyHeadSecond.Next
    	}
    	return dummyHeadFirst.Next
    }
    

Log in to reply
 

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