这个链表分区算法是如何工作的？

Question

我现在正在读《破解编码面试》一书，这本书提出了一个链表划分问题：

Given a linked list and a value x, partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

假设链接列表不是空的

The solution取自Geeksforgeks网站，与CTCI一书中提供的第二种解决方案相同：

// Function to make a new list  
// (using the existing nodes) and  
// return head of new list.  
static Node partition(Node head, int x)  
{  
    /* Let us initialize start and tail nodes of new list */
    Node tail = head;  
  
    // Now iterate original list and connect nodes  
    Node curr = head;  
    while (curr != null)  
    {  
        Node next = curr.next;  
        if (curr.data < x)  
        {  
            /* Insert node at head. */
            curr.next = head;  
            head = curr;  
        }  
  
        else // Append to the list of greater values  
        {  
            /* Insert node at tail. */
            tail.next = curr;  
            tail = curr;  
        }  
        curr = next;  
    }  
    tail.next = null;  
  
    // The head has changed, so we need  
    // to return it to the user.  
    return head;  
}

我不明白这个解决方案。这个算法是如何工作的？为什么这是正确的

Answer 1

试着这样想：

假设这是我们的链表(0) -> (1) -> (2) -> (-1) -> (1) -> (-5)（显然，链表看起来不是这样的，只是我们的例子）

和x = 0

我们这样做是为了不“丢失”下一个节点

\n我要从头到尾做记号

现在我们来看一下（0），它是否小于x并不重要（bcs它的头部和尾部），所以它的指针指向它自己

[*^(0)<  ] [  (1) -> (2) -> (-1) -> (1) -> (-5) ]

现在我们来看（1）它也不小于x，所以（0）指向它，它变成了^尾

[ *(0) -> ^(1)< ] [ (2) -> (-1) -> (1) -> (-5) ]（这两个列表附在后面，但让我们想象一下它们没有）

同样的事情也发生在（2）^尾巴上，它是（1）指向它的

[ *(0) -> (1) -> ^(2)<  ] [  (-1) -> (1) -> (-5) ]

现在我们看一下（-1），但是这次它比x小，所以它被设置为指向*head，然后设置为*head

[ *(-1) -> (0) -> (1) -> ^(2)<  ] [  (1) -> (-5) ]

等等：

[ *(-1) -> (0) -> (1) -> (2) -> ^(1)<  ] [ (-5) ]

[ *(-5) -> (-1) -> (0) -> (1) -> (2) -> ^(1)<  ] [ ]