鏈接列表反向沒有臨時

有沒有什麼辦法可以反轉鏈接列表，而不使用C中的臨時變量？在此先感謝。鏈接列表反向沒有臨時

著名的辦法：

Element *reverse(Element *head) 
{ 
    Element *previous = NULL; 

    while (head != NULL) { 
     // Keep next node since we trash 
     // the next pointer. 
     Element *next = head->next; 

     // Switch the next pointer 
     // to point backwards. 
     head->next = previous; 

     // Move both pointers forward. 
     previous = head; 
     head = next; 
    } 

    return previous; 
}

使用臨時變量

SAURABH

來源

2012-01-11 Saurabh Ghorpade

如何遞歸呢？ – 2012-01-11 22:24:46

遞歸是一種騙局，因爲參數本質上是臨時變量。 – 2012-01-11 22:35:50

同意，但這通常是像這個一樣的語義呃問題。 – 2012-01-11 22:37:12

請注意，您的temp的使用實際上是產生兩個swap()通話，並且可以替換爲：

swap(head->next,previous); 
swap(previous,head);

您可以在不使用XOR臨時工交換，它被稱爲xor swap。

來源

2012-01-11 22:29:47 amit

使用XOR-swaps上的指針假的XOR-linked-list.

實現留給讀者作爲一個練習。

來源

2012-01-11 22:25:04

遞歸方法：

Element *reverse(Element *head, Element **first) 
{ 
    if (head->next == NULL) 
    { 
     *first = head; 
     return head; 
    } 


    Element* NextElement= reverse (head->next, first); 
    NextElement->next = head; 
    head->next = null; 

    return head; 
}

徵集遞歸函數：

Element *revLinkListHead; 
    reverse(head, &revLinkListHead);

來源

2012-06-05 13:30:07 Sach

如果有人仍然有興趣，這裏是不使用新的變量可言，除了那些在遞歸傳遞的解決方案呼叫。

public static List invert(List l) { 
    invert(l.next, l, l); 
    l = l.next; 
    breakCycle(l, l); 
    return l; 
} 

private static void invert(List l, List toBeNext, List first) { 
    if(l.next == null) { 
     l.next = toBeNext; 
     first.next = l; 
    } else { 
     invert(l.next, l, first); 
     l.next = toBeNext; 
    } 
} 

private static void breakCycle(List l, List first) { 
    if(l.next == first) { 
     l.next = null; 
    } else { 
     breakCycle(l.next, first); 
    } 
}

的想法是這樣的：第一，我們運行反向功能遞歸，並執行它，這樣，當它達到其分配爲當期頭的下一個元素的最後一個元素（參數first）。在我們執行它之後，我們將有一個反轉列表，但循環，所以當前head.next將指向反轉列表的頭部。我們重新分配下一個元素（反向列表的實際首長），我們最後要做的就是打破這個循環。所以我們稱之爲breakCycle這是遞歸的工作！

來源

2014-11-30 12:25:54 heorhi

鏈接列表反向沒有臨時

回答

相關問題