java - 单向链表中的分区

Question

我正在做这个练习:

编写代码围绕值 x 对链表进行分区，这样所有小于 x 的节点都排在所有大于或等于 x 的节点之前。示例输入:3 -> 5 -> 8 -> 5 -> 10 -> 2 -> 1 输出:3 -> 1 -> 2 -> 10 -> 5 -> 5 -> 8

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

    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(头部)和一个 int(大小)。 LinkedListNode 包含两个属性:一个是指向下一个节点的 LinkedListNode 类型，另一个是 int 类型:数据值

谢谢。

Answer 1

您的代码的问题不是您提到的合并两个列表。在这里使用 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;
}

希望对您有所帮助!