Aufteilen einer LinkedList

Question

Angenommen, ich habe eine verknüpfte Liste wie 1 -> 2 -> 3 -> 4 -> 5. Ich möchte m _th Element und von m+1 _th bis zum Ende dieses verketteten Liste von dem ersten Element trennen, so dass für m=2 wir 1 -> 2 und 3 -> 4 -> 5, so etwas wie dieses haben würde:

private ListNode split(ListNode head, int m) { 
    ListNode h1 = new ListNode(0); 
    ListNode h2 = new ListNode(0); 

    h1.next = head; 
    h2.next = head; // same reference: error! 

    ListNode cur1 = h1; 
    ListNode cur2 = h2; 

    for (int i = 0; i < m; i++) { 
     cur1 = cur1.next; 
    } 
    cur1.next = null; 

    ListNode tmp = cur2.next; 
    for (int i = 0; i < m; i++) { 
     tmp = tmp.next; 
    } 
    cur2.next = tmp; 

    // doesn't matter which one to return 
    return h2.next; 
} 

Ich weiß, das funktioniert nicht, weil ich die gleiche Referenz (head) für meine h2 benutze und ich muss eine Kopie des Kopfes machen (h2.next = copyOfHead), aber ich frage mich, ob es eine bessere, effizientere Lösung gibt, ohne eine Kopie davon zu machen Kopf.

Answer 1

Ich glaube, Sie nur einen Knoten Verweis auf den Kopf benötigen

vom Kopf Starten, wenn Sie die „Start“ -Liste so die n ten Knotenpunkte auf null (und damit „Splitting“) ändern Sie dann Geben Sie den Knoten n+1 zurück, der den Rest der Liste enthält.

Ich stelle mir vor, so etwas wie dieses

private ListNode split(ListNode head, int m) { 

    ListNode tmp = head; 
    // Additionally check that you don't go beyond the list 
    for (int i = 0; tmp.next != null && i < m; i++) { 
     tmp = tmp.next; 
    } 

    ListNode remainder = tmp.next; 
    tmp.next = null; 

    return remainder; 
}