algorithm - 对链表进行分区

Question

我试图解决这个基于链表数据结构的算法问题。问题如下:

给定一个链表和一个值 x，对其进行分区，使所有小于 x 的节点排在大于或等于 x 的节点之前。 您应该保留两个分区中每个分区中节点的原始相对顺序。

例如，

给定 1->4->3->2->5->2 且 x = 3， 返回 1->2->2->4->3->5.

我的解决方案是:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head == null) return null;
        ListNode headNode = new ListNode(-1);
        headNode.next = head;

        ListNode tail = head;
        while(tail.next!=null){
            tail = tail.next;
        }
        ListNode actualTail = tail;
        ListNode current = headNode;
        while(current!=actualTail && current.next!=actualTail){
            if(current.next.val >= x && current.next!=tail){
                System.out.println("Moving "+current.next.val+" to end of list, ahead of "+tail.val);
                ListNode temp = current.next;
                current.next = current.next.next;
                tail.next = temp;
                tail = tail.next;
                tail.next = null;
            }else{
                current = current.next;    
            }

        }
        return headNode.next;
    }
}

虽然一些测试用例使用此代码(例如上面提到的代码)运行良好，但有一组测试用例失败了，因为我无法维持列表中节点的原始相对顺序。

例如: 列表 = [1->2] x = 0

我的结果: [2,1]

预期: [1,2]

如有任何帮助，我们将不胜感激。

Answer 1

我认为你可以用更简单的方式来做:

• 保留 2 个列表，一个用于较低节点，另一个用于较大节点。
• 迭代列表，将节点添加到相应的列表。
• 将较低的列表与较高的列表连接起来

像这样:

public ListNode Partition(ListNode head, int x)
{
    ListNode lowerHead = null, lowerTail = null;              //Head and Tail of lower list
    ListNode greaterHead = null, greaterTail = null;          //Head and Tail of greater list

    ListNode current = head;

    while (current != null)
    {
        if (current.val < x)
        {
            if (lowerHead == null) lowerHead = current;      //If is the first node in the list
            if (lowerTail == null) lowerTail = current;      //set the head an tail to the same value
            else lowerTail = lowerTail.next = current;       //Otherwise, add the node and update the tail
        }
        else
        {
            if (greaterHead == null) greaterHead = current;  //If is the first node in the list
            if (greaterTail == null) greaterTail = current;  //set the head an tail to the same value
            else greaterTail = greaterTail.next = current;   //Otherwise, add the node and update the tail
        }

        current = current.next;
    }

    if (greaterHead != null)
        greaterTail.next = null;

    if (lowerHead == null) return greaterHead;
    else
    {
        lowerTail.next = greaterHead;
        return lowerHead;
    }
} 

因为节点是按照它们出现在原始列表中的方式添加的，所以顺序得以保留