86. Partition List

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

---

本题要求把链表中小于某个数的节点移到大于等于某个数的节点前面，要求两个部分中的节点的相对顺序不变。 思路很简单，维护两个链表，一个是小于x的，另一个是大于等于x的，然后遍历原链表，分别把小于和大于等于x的节点接到对应的链表上。最后记得把第一个链表的尾部连到第二个链表的头部，然后第二个链表的尾节点置空。 完整代码如下：

class Solution {
public:
    ListNode* partition(ListNode* head, int x)
    {
        ListNode *head1 = new ListNode(0), *head2 = new ListNode(0);
        ListNode *prior1 = head1, *prior2 = head2;
        while (head != NULL) {
            if (head->val < x) {
                prior1->next = head;
                prior1 = prior1->next;
            }
            else {
                prior2->next = head;
                prior2 = prior2->next;
            }
            head = head->next;
        }
        prior2->next = NULL;
        prior1->next = head2->next;
        return head1->next;
    }
};

本代码提交AC，用时6MS。