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.