java - 围绕值对链表进行分区

Question

我正在阅读一本编码书，出现了这个问题:

编写代码以值 x 为中心对链表进行分区，使得所有小于 x 的节点都位于所有大于或等于 x 的节点之前。

该解决方案涉及两个列表。

如果这是一个数组，我们需要小心如何移动元素。大批轮类非常昂贵。然而，在链表中，情况就容易多了。而不是转移和交换元素，我们实际上可以创建两个不同的链表:一个用于小于 x 的元素，1 表示大于或等于 x 的元素。我们遍历链表，将元素插入到我们的 before 列表或 after 列表中列表。一旦我们到达链表的末尾并完成了分割，我们合并两个列表。

1 /* Pass in the head of the linked list and the value to partition
2 * around */
3 public LinkedListNode partition(LinkedListNode node, int x) {
4     LinkedListNode beforeStart = null;
5     LinkedListNode beforeEnd = null;
6     LinkedListNode after-Start = null;
7     LinkedListNode afterEnd = null;
8 
9    /* Partition list */
10     while (node != null) {
11         LinkedListNode next = node.next;
12         node.next = null;
13         if (node.data < x) {
14             /* Insert node into end of before list */
15             if (beforeStart == null) {
16                 beforeStart = node;
17                 beforeEnd = beforeStart;
18                 } else {
19                     beforeEnd.next = node;
20                     beforeEnd = node;
21                 }
22             } else {
23             /* Insert node into end of after list */
24             if (after-Start == null) {
25                 afterStart = node;
26                 afterEnd = afterStart;
27             } else {
28                 afterEnd.next = node;
29                 afterEnd = node;
30             }
31         }
32         node = next;
33     }
34
35     if (beforeStart == null) {
36         return afterStart;
37     }
38
39     /* Merge before list and after list */
40     beforeEnd.next = afterStart;
41     return beforeStart;
42 }

我的问题是这样的 - 必须创建几个新的 LinkedList 来进行合并，这看起来不是有点浪费空间吗？难道一切都不能就地完成吗？这是我的实现。

Node partition(Node head, int x) {
    Node realhead = head;
    Node iter = head;
    while(iter != null && iter.next != null) {
        if(iter.next.data < x) {
            Node temp = iter.next;
            iter.next = temp.next;
            temp.next = realhead;
            realhead = temp;
        }
        iter = iter.next;
    }
    return realhead;
} 

这应该(理论上)提供 O(n) 性能，与书中的解决方案一样好，但具有 O(1) 空间，因为它不使用任何额外的数据结构，并且只使用几个额外的指针。除非这本书只是寻求一个次优的解决方案，否则我在实现中肯定遗漏了一些东西。谁能指出我的错误吗？

Answer 1

这是我的 Java 解决方案。

/*
 * Append a new node to the end of a LinkedList
 */
private static Node appendNode(Node head, int data)
{
    // If head is null, then add the first node
    if(head == null)
        return new Node(data);      

    Node runner = head;
    while(runner.next != null)
        runner = runner.next;

    runner.next = new Node(data);

    return head;
}

private static Node concatenate(Node head, Node tail)
{
    // First, check arguments whether they are null or not
    if(head == null && tail == null)
        return null;

    if(head == null)
        return tail;

    if(tail == null)
        return head;

    Node runner = head;
    while (runner.next != null)
    {
        runner = runner.next;
    }

    runner.next = tail;

    return head;
}

/*
 * Partition a LinkedList
 */
private static Node partition(Node head, int x)
{
    if(head == null)
        return null;

    Node runner = head;
    Node left = null;
    Node right = null;

    while (runner != null)
    {
        if(runner.data < x)
        {
            if(left == null)
                left = new Node(runner.data);
            else
                left = appendNode(left, runner.data);
        }
        else
        {
            if(right == null)
                right = new Node(runner.data);
            else
                right = appendNode(right, runner.data);
        }
        runner = runner.next;
    }

    Node partitioned = concatenate(left, right);

    return partitioned;
}