86. Partition List #

Problem #

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.

Example:


Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

Problem Summary #

Given a number x, all numbers greater than or equal to x should be arranged after numbers less than x, and their relative positions must not change. Since the relative positions cannot change, we cannot use an idea similar to bubble sort.

Solution Approach #

The simplest way to solve this problem is to construct a doubly linked list, but the time complexity is O(n^2).

(In the following description, those greater than or equal to x are all considered greater than x)

A better method is to construct 2 new linked lists: one linked list specifically stores nodes less than x, and the other specifically stores nodes greater than x. Starting from the head of the original linked list, scan once and classify these two types of nodes into the 2 newly created linked lists in order, somewhat like pushing onto a stack. Since the original linked list is scanned from the head, the original order in the original linked list will still be preserved. Finally, the 2 new linked lists will store their respective results; by concatenating these two linked lists, putting the linked list less than x in front of the linked list greater than x, the final answer can be obtained.

Code #


package leetcode

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// Solution 1: singly linked list
func partition(head *ListNode, x int) *ListNode {
	beforeHead := &ListNode{Val: 0, Next: nil}
	before := beforeHead
	afterHead := &ListNode{Val: 0, Next: nil}
	after := afterHead

	for head != nil {
		if head.Val < x {
			before.Next = head
			before = before.Next
		} else {
			after.Next = head
			after = after.Next
		}
		head = head.Next
	}
	after.Next = nil
	before.Next = afterHead.Next
	return beforeHead.Next
}

// DoublyListNode define
type DoublyListNode struct {
	Val  int
	Prev *DoublyListNode
	Next *DoublyListNode
}

// Solution 2: doubly linked list
func partition1(head *ListNode, x int) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	DLNHead := genDoublyListNode(head)
	cur := DLNHead
	for cur != nil {
		if cur.Val < x {
			tmp := &DoublyListNode{Val: cur.Val, Prev: nil, Next: nil}
			compareNode := cur
			for compareNode.Prev != nil {
				if compareNode.Val >= x && compareNode.Prev.Val < x {
					break
				}
				compareNode = compareNode.Prev
			}
			if compareNode == DLNHead {
				if compareNode.Val < x {
					cur = cur.Next
					continue
				} else {
					tmp.Next = DLNHead
					DLNHead.Prev = tmp
					DLNHead = tmp
				}
			} else {
				tmp.Next = compareNode
				tmp.Prev = compareNode.Prev
				compareNode.Prev.Next = tmp
				compareNode.Prev = tmp
			}
			deleteNode := cur
			if cur.Prev != nil {
				deleteNode.Prev.Next = deleteNode.Next
			}
			if cur.Next != nil {
				deleteNode.Next.Prev = deleteNode.Prev
			}
		}
		cur = cur.Next
	}
	return genListNode(DLNHead)
}

func genDoublyListNode(head *ListNode) *DoublyListNode {
	cur := head.Next
	DLNHead := &DoublyListNode{Val: head.Val, Prev: nil, Next: nil}
	curDLN := DLNHead
	for cur != nil {
		tmp := &DoublyListNode{Val: cur.Val, Prev: curDLN, Next: nil}
		curDLN.Next = tmp
		curDLN = tmp
		cur = cur.Next
	}
	return DLNHead
}

func genListNode(head *DoublyListNode) *ListNode {
	cur := head.Next
	LNHead := &ListNode{Val: head.Val, Next: nil}
	curLN := LNHead
	for cur != nil {
		tmp := &ListNode{Val: cur.Val, Next: nil}
		curLN.Next = tmp
		curLN = tmp
		cur = cur.Next
	}
	return LNHead
}