我现在正在阅读Cracking the Coding Interview这本书，它提出了一个链表分区问题：

给定一个链表和一个值 x，围绕一个值 x 划分一个链表，使得所有小于 x 的节点排在所有大于或等于 x 的节点之前。

假设链表不为空。

The solution 取自 GeeksForGeeks 网站，与 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;  
}

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