Блог

Прямо сейчас я читаю книгу Cracking the Coding Interview, в которой представлена проблема с разделением связанного списка:

Учитывая связанный список и значение x, разделите связанный список вокруг значения x таким образом, чтобы все узлы, меньшие, чем x, предшествовали всем узлам, большим или равным x.

Предположим, что связанный список не пуст.

Решение взято с веб-сайта 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;  
}
 

Я не понимаю этого решения. Как работает этот алгоритм? Почему это правильно?

Попробуйте подумать примерно так:

Допустим, это наш связанный список (0) -> (1) -> (2) -> (-1) -> (1) -> (-5) (очевидно, что связанные списки выглядят не так, но для нашего примера)

И x = 0

Мы делаем next = curr.next так, чтобы не «потерять» следующий узел

Я собираюсь отметить *head и ^tail

Теперь мы смотрим на (0), не имеет значения, меньше ли оно x (bcs его голова и хвост), поэтому его указатель повернут на себя

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

Теперь мы смотрим на (1), который также не меньше x, поэтому (0) указывает на него, и он становится ^tail

[ *(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)<  ] [ ]