左右交換循環鏈表節點

基本上我必須把一個循環鏈表中的一組節點移動到同一個鏈表中的不同點上。左右交換循環鏈表節點

 prev ptr

[1] - > [2] - > [3] - > [4]
< ------------------- -
假設我想在3和4之間移動1和2，並將4個圓圈重新設置爲3.我有指向1（temp1），3（temp3）和4 我認爲這些是操縱的重要指針，所以我爲他們設置臨時工。

如何設置prev和ptr指針與溫度指針協調？這很混亂，我把所有的組合放在一起，並嘗試打印列表，它會讓我陷入無限循環。我想了解一個在接近這個精確的方法。謝謝。

來源

2011-02-11 Jimmy James

將操作視爲兩種不同的操作可能會更容易。刪除，然後插入。

// remove the node 
Node node = ...; // whatever identifies the node to operate on 
prev(node).setNext(next(node)); 

// insert it into its new position 
Node newPrev = ...; // whatever identifies the node to operate on 
Node newNext = newPrev.next(); 
newPrev.setNext(node); 
node.setNext(newNext);

來源

2011-02-11 06:42:26 enonu

這就是我正在建議的。然後，當然，這些操作應該被包裝在自己的函數中，看起來像`llRemove（LIST * list，NODE * node）`和'llAdd（LIST * list，NODE * node，NODE *）` – 2011-02-11 06:49:10

注意enonu的做法並不在某些特殊情況下工作，如果一個結點是旁邊的其他，或者它們指的是同一節點等。

以下方法通過觀察在P交換兩個節點A和B _甲，A和S _乙的前身，B.第一的後繼者，除去A和B，然後我們插入S的左_B最後B的右側P _A。在A是B的後繼者的特殊情況下，我們使用交換的參數重新啓動。如果兩者都是彼此的繼承者，我們什麼也不做。

private void swap(Node a, Node b) { 
    if (a.pred == b) { 
     if (b.pred != a) 
      swap(b, a); 

     return; 
    } 

    Node pa = a.pred, sb = b.succ; 

    // remove a from list 
    pa.succ = a.succ; 
    pa.succ.pred = pa; 

    // remove b from list 
    sb.pred = b.pred; 
    sb.pred.succ = sb; 

    // add a before sb 
    a.pred = sb.pred; 
    a.succ = sb; 
    a.pred.succ = a; 
    a.succ.pred = a; 

    // add b after pa 
    b.succ = pa.succ; 
    b.pred = pa; 
    b.pred.succ = b; 
    b.succ.pred = b; 
}

來源

2014-06-18 11:20:06 fuz

左右交換循環鏈表節點

回答

相關問題