Partitiom List Sorted
出处
Given a linked list and a value x, write a function to reorder this list such that all nodes less than x come before the nodes greater than or equal to x.
给定一个单链表和数值x,划分链表使得所有小于x的节点排在大于等于x的节点之前。
你应该保留两部分内链表节点原有的相对顺序。
样例
给定链表 1->4->3->2->5->2->null,并且 x=3
返回 1->2->2->4->3->5->null
Solution
将链表分成两部分,但这两部分的头节点连是不是NULL都不确定。当涉及对头节点的操作,我们不妨考虑创建哑节点。这样做的好处是:我们总是可以创建两个哑节点,用dummy->next作为真正头节点的引用, 然后在此基础上append,这样就不用处理头节点是否为空的边界条件了。
Complexity
实际上只需要遍历链表一次,所以复杂度是 O(n)
Code
Node reorderList(Node head, int x){
if (head == null) return null;
Node small = new Node(-1);
Node sback = small;
Node large = new Node(-1);
Node lback = large;
while (head != null){
Node next = head.next;
head.next = null;
if (head.value < x){
small.next = head;
small = small.next;
} else {
large.next = head;
large = large.next;
}
head = next;
}
small.next = lback.next;
return sback.next;
}