Разделение связанного списка

Question

Я пытаюсь решить эту алгоритмическую проблему на основе структуры связанных списков. Вопрос заключается в следующем:

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

Например,

Учитывая, 1-> 4-> 3-> 2-> 5-> 2 и х = 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] х = 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; 
    } 
} 

сохраняется заказ, так как узлы добавляются, как они появляются в исходном списке