反向鏈接列表算法

我做了一個算法，應該顛倒我的鏈表。原始列表看起來像7 5 6我想將其轉換爲5 6 7。但反向功能後，打印出鏈表時，我只看到5反向鏈接列表算法

NodeType * temp = start; 
int dataHolder[length] = {0}; 
int runTime = length - 1; 

for(int i = 0; i<length; i++){ 
    if(temp->next == NULL){ 
     break; 
    } 

    dataHolder[runTime] = temp->data; 
    temp = temp->next; 
    runTime--; 
} 

for(int j = 0; j<length; j++){ 
    if(start->next == NULL){ 
     break; 
    } 

    start->data = dataHolder[j]; 
    start = start->next; 
}

來源

2017-06-22 ThatOneCoderDude

你的意思是「我想將它反向'6 5 7'」？ –

兩個迴路缺少一個元素，你應該迭代直到當前節點爲NULL，直到下一個節點爲止。實際上，您可以將該條件放在while循環中，而不是使用for循環，這對於鏈接列表可能更合理（即使您已經預先計算了長度）。此外，我懷疑你正在使用相同的start變量來檢查結果，因爲你覆蓋它而不起作用。嘗試是這樣的：

NodeType * temp = start; 
int dataHolder[length] = {0}; 
int runTime = length - 1; 

while (temp != NULL) { 
    dataHolder[runTime] = temp->data; 
    temp = temp->next; 
    runTime--; 
} 

temp = start; 
runtime = 0; 
while (temp != NULL) { 
    temp->data = dataHolder[runtime]; 
    temp = temp->next; 
    runtime++; 
}

附錄：

實際上，你可以不使用任何額外的內存（並無需預先計算它的長度）扭轉O（n）的一個鏈表，只是通過重新排序指針。在某些情況下，這可能是不可接受的（例如，如果您有外部指針或對節點的引用，當您反轉列表時，希望看到它們的值發生變化），但大多數情況都沒有問題。它會去是這樣的：

NodeType * temp1 = start; // Assuming start is not NULL 
NodeType * temp2 = start->next; 
start->next = NULL; 

while (temp2 != NULL) { 
    NodeType * temp3 = temp2->next; 
    temp2->next = temp1; 
    temp1 = temp2; 
    temp2 = temp3; 
}

來源

2017-06-22 13:55:01 jdehesa

你的算法是行不通的，因爲在第一循環數據在第n-1個節點到陣列dataHolder 和複製然後在第二個循環中按照您檢索的順序將數組複製到鏈接列表中。

再加上你正在編輯你的「開始」變量，它是到列表

開始時只參考在第二循環開始點結束的倒數第二個節點列表

和您使用相同的顯示鏈表「start」變量

您輸入的數據
7-> 5> 6
中時，dataHolder處理第一環後
將其複製到鏈接列表中。鏈表現在
7-> 5
但開始指向5

顯示使用開始鏈表如此明顯 5只打印

來源

2017-06-22 13:53:14

反向鏈接列表算法

回答

相關問題