Partitionierung einer verketteten Liste

Question

Ich versuche dieses algorithmische Problem zu lösen, basierend auf der Datenstruktur der verknüpften Liste. Die Frage ist wie folgt:

Gegeben eine verkettete Liste und ein Wert x, Partition es so, dass alle Knoten kleiner als x kommen vor Knoten größer als oder gleich x. Sie sollten die ursprüngliche relative Reihenfolge der Knoten in jeder der beiden Partitionen beibehalten.

Zum Beispiel

Gegeben 1-> 4> 3> 2> 5-> 2 und x = 3, return 1-> 2> 2> 4- > 3-> 5.

zum Problem Meine Lösung ist:

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

Während einige Testfälle arbeiten mit diesem Code wie der feinen oben erwähnt, gibt es eine Reihe von Testfällen, die in, dass ich nicht in der Lage ausfallen, bin um die ursprüngliche relative Reihenfolge der Knoten in der Liste beizubehalten.

Zum Beispiel: list = [1-> 2] x = 0

Mein Ergebnis: [2,1]

Erwartet: [1,2]

All Hilfe würde sehr geschätzt werden.

Answer 1

Ich glaube, Sie es auf einfachere Art und Weise tun:

• 2 Listen halten, einen für untere Knoten und andere für mehr Knoten.
• Iterieren Sie die Liste, indem Sie die Knoten zur entsprechenden Liste hinzufügen.
• verketten die untere Liste mit mehr Liste

Etwas wie folgt aus:

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

Auftrag erhalten wird, da Knoten hinzugefügt werden, wie sie in der ursprünglichen Liste erscheinen