在給定節點之間反轉雙鏈表

Question

嘗試反轉給定指向鏈表中給定節點的鏈接列表元素。 例如，我會得到一個指向第4個的指針和一個指向鏈表中第7個節點的指針，並且必須反轉這些節點之間的節點。下面是一些不起作用的相關代碼：

template <class T> 
void List<T>::reverse(ListNode * & startPoint, ListNode * & endPoint){ 

    if (startPoint == NULL) 
    return; 

    if (startPoint->prev != NULL) 
    startPoint->prev->next = endPoint; 

    if (endPoint->next != NULL) 
    endPoint->next->prev = startPoint; 

    ListNode * curr = startPoint; 
    ListNode * temp = startPoint; 

    while(curr != endPoint) 
    { 
    temp = curr->next; 
    curr->next = curr->prev; 
    curr->prev = temp; 
    curr = temp; 
    } 

    temp = endPoint->next; 
    endPoint->next = endPoint->prev; 
    endPoint->prev = temp; 

    temp = startPoint->next; 
    startPoint->next = endPoint->next; 
    endPoint->prev = startPoint->prev; 

    temp = startPoint; 
    startPoint = endPoint; 
    endPoint = temp; 

} 

此代碼編譯但沒有正確執行反向節點，我不知道爲什麼。

Answer 1

我還沒有嘗試過編碼，但算法上這應該是相當快的;

1）首先從您的子列表的起始位置和結束位置之間的所有節點交換prev和next的值。這將顛倒它們之間的所有節點的順序。僅留下邊緣節點。

2）在所有位置交換next和prev之後，還將原始開始節點的更新下一個交換與原始結束節點的更新prev進行交換。現在這些節點將指向序列的正確剩餘部分。

3）for management還更新了正好在序列外部的節點以正確指向。

一個例子（節點示出爲 「NODE（PREV，NEXT）」）

A(0,B) - B(A,C) - C(B,D) - D(C,E) - E(D,F) - F(E,-) 

反轉節點1 - 4（B - E）

第一步：

A(0,B) - B(C,A) - C(D,B) - D(E,C) - E(F,D) - F(E,-) 

2nd

A(0,B) - B(C,F) - C(D,B) - D(E,C) - E(A,D) - F(E,-) 

A(0,E) - B(C,F) - C(D,B) - D(E,C) - E(A,D) - F(B,-) 

現在以可視化的順序：

A(0,E) - E(A,D) - D(E,C) - C(D,B) - B(C,F) - F(B,-) 

它就在那裏，扭轉了中間4個節點。