如何更新循環鏈表中的尾部？

Question

如果我在初始後方移動一組節點，我需要幫助更新循環鏈表的後部。

讓我們假設後方是後方的節點，後方的方向則返回到[1]。

[1][2][3][4][5] 
<-------------/ 

如果我提出[1][2][3]後節點[5]給我

[4][5][1][2][3]，它打破了循環鏈表，

我怎樣才能接近更新[3]作爲後方和rear.next指向[1]？

Answer 1

由於鏈接集的性質是一個圓圈，因此您必須拆除鏈接並在移動後重新建立鏈接。這裏的重要鏈接是將被「破壞」的鏈接，它是（如果它是單鏈表，正如我所假設的那樣），從[3] -> [4]的鏈接和從[5] -> [1]的鏈接。

你在你的列表中有兩個部分在這裏，[1][2][3]，我們可以稱之爲A和[4][5]，我們可以稱之爲B。下面顯示的-->鏈接是指向列表中第一個元素的指針。

--> A -> B -+ 
    ^  | 
    |  | 
    +-------+ 

你想要做的是重新設置鏈接，以便在A指向第一個元素的最後一個元素的B，並在B指向第一個元素A最後一個元素。此外，在列表的開始，現在是B.

--> B -> A -+ 
    ^  | 
    |  | 
    +-------+ 

第一要素所以現在我們只是打破和重新需要它們的鏈接。

--> [1][2][3] -> [4][5] -+   --> [4][5] -> [1][2][3] -+ 
    ^     | =>  ^     | 
    +-------------------+    +-------------------+ 

• 設置列表的開始是B的第一要素，這是[4]
• 坐落在B的最後一個元素，這是[5]，指向第一個元素A，該是[1]。這恰好已經是這樣設定的，但不要指望這一點。 :)
• 將A中的最後一個元素設置爲[3]，以指向B中的第一個元素，即[4]。

正如你可以看到，我們真正關心的只是節點列表，即開始各部分的第一個和最後一個元素和A和B結束元素。在這種情況下，其中一個部分也包含第一個元素，所以我們必須移動哪個元素是'第一個'元素的概念。希望這可以幫助。

Answer 2

這功課嗎？

你是如何做「移動」？

我會使它成爲一個函數，如list.move(first, last, after)，在這種情況下，它將是list.move(1, 3, 5)。

而且你會有變量跟蹤列表的前面/頭部和尾部/尾部。我會假設他們叫list.front和list.rear。

因此，在任何情況下，你想做的事：

list[after].next = list[first] 

，然後有兩種特殊情況下，我可以看到：

插入後後
（ list[after] == list.rear）

移動

• 頭
  （list[start] == list.front）

因此，您可以使用if語句處理這些語句。

Answer 3

我覺得這回答它（只要我明白這個正確）

Node insertAtRear(Node rear, T value) { 
    Node tmp = new Node(value); 
    if(rear!=null) { 
    tmp.next = rear.next; 
    rear.next = tmp 
    rear = tmp 
    } else { 
    // this is probably the first element to be inserted 
    rear = tmp; 
    rear.next = rear; 
    } 
} 

Answer 4

開始時使用的基礎上，工作[1] [2] [3] [4] [5]，你想結束[4] [5] [1] [2] [3]你可以使用指針來做到這一點，而不是改變數據結構。

正如您已經指出的那樣，我們有一個循環列表，其中指針「rear.next」指向第一個存儲桶，並且每個後續存儲段都有一個.next指針，將其鏈接到其最右邊的鄰居，直到我們返回到後部存儲桶再次。基本上是一堆相互關聯的桶。

如果我們創建一個「尾」節點和一個「頭」節點，我們可以使用它們來排序列表。這些是標記，而不是它們剛剛指向開始或結束點的圓圈的一部分。爲了得到[1] [2] [3] [4] [5]，我們可以設置尾節點指向[5]，然後跟隨[5]的下一個指針，它將我們引導到[1]，其中我們將我們的標題設置爲指向。所以header = [1]; tail = [5]

從頭文件開始，遍歷下一個指針後的列表，每次我們都可以按照這個順序訪問我們的項目[1] [2] [3] [4 ] [5]。那裏沒有驚喜！

讓我們改變，雖然我們想要[3]是後方。所以讓我們設置我們的尾節點指向[3]。然後按照[3]的下一個指針我們到達[4]。爲此，我們分配頭部。因此，頭部= [4];尾部= [3]

現在通過我們的名單開始我們的標題指向我們[4] [5] [1] [2] [ 3]。

看來我們已經執行了移動操作，但我們並沒有篡改數據結構或其鏈接 - 就像我們使用它的方式一樣。我們所有改變的是我們的頭和尾巴。 （我們的指針）。這就是通告清單的美妙之處。