单链表中的分区

Question

我在做这个练习：

编写代码将链表围绕值x分区，使得所有小于x的节点都排在所有大于或等于x的节点之前。示例输入：3-

我发现很难找到单一链表（由我自己创建，不使用库）的解决方案，我想知道我的代码中是否有不必要的代码块，是否有办法避免放入两个链表然后合并？因为它似乎有非常慢的性能。

    public CustomLinkedList partition(CustomLinkedList list, int x) {
    CustomLinkedList beforeL = new CustomLinkedList();
    CustomLinkedList afterL = new CustomLinkedList();
    LinkedListNode current = list.getHead();
    while (current != null) {
        if (current.getData() < x) {
            addToLinkedList(beforeL, current.getData());
        } else {
            addToLinkedList(afterL, current.getData());
        }
        // increment current
        current = current.getNext();
    }
    if (beforeL.getHead() == null)
        return afterL;
    mergeLinkedLists(beforeL, afterL);
    return beforeL;
}

public void addToLinkedList(CustomLinkedList list, int value) {
    LinkedListNode newEnd = new LinkedListNode(value);
    LinkedListNode cur = list.getHead();
    if (cur == null)
        list.setHead(newEnd);
    else {
        while (cur.getNext() != null) {
            cur = cur.getNext();
        }
        cur.setNext(newEnd);
        cur = newEnd;
    }
}

public void mergeLinkedLists(CustomLinkedList list1, CustomLinkedList list2) {
    LinkedListNode start = list1.getHead();
    LinkedListNode prev = null;
    while (start != null) {
        prev = start;
        start = start.getNext();        
    }
    prev.setNext(list2.getHead());
}

CustumLinkedList包含两个属性：-LinkedListNode是head，int是size。LinkedListNode包含两个属性：一个是指向下一个节点的LinkedListNode类型，另一个是int:data value类型

非常感谢。

Answer 1

我认为保留两份清单不是问题。可以使用单个列表，但代价是失去一些简单性。

主要问题似乎是addToLinkedList（CustomLinkedList，int-value）方法。

它遍历整个列表，以便添加新元素。

另一种选择是始终在列表的前面添加元素。这也将产生一个有效的解决方案，并将运行得更快。

Answer 2

如果您有任何数据列表，请访问orderByX方法。希望对你有帮助。

public class OrderByX {
Nodes root = null;

OrderByX() {
    root = null;
}

void create(int[] array, int k) {
    for (int i = 0; i < array.length; ++i) {
        root = insert(root, array[i]);
    }
}

Nodes insert(Nodes root, int data) {
    if (root == null) {
        root = new Nodes(data);
    } else {
        Nodes tempNew = new Nodes(data);
        tempNew.setNext(root);
        root = tempNew;
    }
    return root;
}

void display() {
    Nodes tempNode = root;
    while (tempNode != null) {
        System.out.print(tempNode.getData() + ",  ");
        tempNode = tempNode.getNext();
    }
}

void displayOrder(Nodes root) {
    if (root == null) {
        return;
    } else {
        displayOrder(root.getNext());
        System.out.print(root.getData() + ",  ");
    }

}

Nodes orderByX(Nodes root, int x) {
    Nodes resultNode = null;
    Nodes lessNode = null;
    Nodes greatNode = null;
    Nodes midNode = null;
    while (root != null) {
        if (root.getData() < x) {
            if (lessNode == null) {
                lessNode = root;
                root = root.getNext();
                lessNode.setNext(null);
            } else {
                Nodes temp = root.getNext();
                root.setNext(lessNode);
                lessNode = root;
                root = temp;
            }
        } else if (root.getData() > x) {
            if (greatNode == null) {
                greatNode = root;
                root = root.getNext();
                greatNode.setNext(null);
            } else {
                Nodes temp = root.getNext();
                root.setNext(greatNode);
                greatNode = root;
                root = temp;
            }
        } else {

            if (midNode == null) {
                midNode = root;
                root = root.getNext();
                midNode.setNext(null);
            } else {
                Nodes temp = root.getNext();
                root.setNext(midNode);
                midNode = root;
                root = temp;
            }

        }
    }
    resultNode = lessNode;
    while (lessNode.getNext() != null) {
        lessNode = lessNode.getNext();
    }
    lessNode.setNext(midNode);
    while (midNode.getNext() != null) {
        midNode = midNode.getNext();
    }
    midNode.setNext(greatNode);
    return resultNode;
}

public static void main(String... args) {
    int[] array = { 7, 1, 6, 2, 8 };
    OrderByX obj = new OrderByX();
    obj.create(array, 0);
    obj.display();
    System.out.println();
    obj.displayOrder(obj.root);
    System.out.println();
    obj.root = obj.orderByX(obj.root, 2);
    obj.display();

}
}

class Nodes {

private int data;
private Nodes next;

Nodes(int data) {
    this.data = data;
    this.next = null;
}

public Nodes getNext() {
    return next;
}

public void setNext(Nodes next) {
    this.next = next;
}

public int getData() {
    return data;
}

public void setData(int data) {
    this.data = data;
}

}

Answer 3

代码的问题不是如您所述合并两个列表。在这里使用单词merge是错误的，因为您只是将左列表的尾部与右列表的头部连接起来，这是一个固定时间操作。

真正的问题是——在左侧或右侧列表中插入新元素时，每次都从头到尾迭代，这会产生总计O（n^2）操作，而且速度肯定很慢。

在这里，我编写了一个更简单的版本，通过跟踪当前的尾部，避免每次从头部迭代以插入新项。

代码非常简单，肯定比您的快（O（n））。如果你需要任何解释，请告诉我。

// I don't know how your CustomLinkedList is implemented. Here I wrote a simple LinkedList node
public class ListNode {
    private int val;
    private ListNode next;
    public ListNode(int x) {
        val = x;
    }
    public int getValue() {
        return this.val;
    }
    public ListNode getNext() {
        return this.next;
    }
    public void setNext(ListNode next) {
        this.next = next;
    }
}

public ListNode partition(ListNode head, int x) {

    if(head == null) return null;

    ListNode left = null;
    ListNode right = null;

    ListNode iterL = left;
    ListNode iterR = right;

    while(iter != null) {

        if(iter.getValue() < x) {
            iterL = addNode(iterL, iter.getValue());
         }
        else {
            iterR = addNode(iterR, iter.getValue());
        }

        iter = iter.getNext();
    }

    // link up the left and right list
    iterL.setNext(iterR);

    return left;
}

public ListNode addNode(ListNode curr, int value) {

    ListNode* newNode = new ListNode(value);

    if(curr == null) {
        curr = newNode;
    } else {
       curr.setNext(newNode);
       curr = curr.getNext();
    }

    return curr;
}

希望有帮助！