对链表进行分区 [英] Partitioning a linked list

问题描述

我正在尝试根据链表数据结构解决此算法问题。问题如下：

I am trying to solve this algorithmic problem based on linked list data structure. The question is as follows:

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

例如，

给出1-> 4-> 3-> 2-> 5-> 2且x = 3，
返回1-> 2- > 2-> 4-> 3-> 5。

我对这个问题的解决方案是：

My solution to the problem is:

/**
 * 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;
    }
}

虽然某些测试用例可以很好地与该代码配合使用，例如上面提到的一个，有一组失败的测试用例，因为我无法维护列表中节点的原始相对顺序。

While some test cases work fine with this code such as the one mentioned above, there are a set of test cases that fail, in that I am unable to maintain the original relative ordering of the nodes in the list.

例如：
list = [1-> 2]
x = 0

For example: list = [1->2] x = 0

我的结果：
[2,1]

My result: [2,1]

期望：
[1,2]

Expected: [1,2]

任何帮助将不胜感激。

推荐答案

我认为您可以通过更简单的方式做到这一点：

I think you can do it in a simpler way:

• 保留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;
    }
} 

由于在节点出现时添加了节点，因此保留了顺序原始列表

Order is preserved since nodes are added as they appear in the original list

这篇关于对链表进行分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！