如何更新循环链表中的后部？

Question

如果我在初始后部之后移动一组节点，我需要帮助更新循环链表的后部。

假设rear是后节点，rear.next循环回到[1]。

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

如果我移动 [1][2][3] 节点 [5] 后给我

[4][5][ 1][2][3]，它打破了循环链表，

如何将[3]更新为rear和rear.next以指向[1] ？

Answer 1

由于链接集的性质是圆形，因此您必须断开链接并在移动后重新建立它们。这里重要的链接是那些将被“破坏”的链接，即（如果它是一个单链表，正如我假设的那样），来自 [3] -> 的链接。 [4] 以及来自 [5] -> 的链接[1]。

您的列表中有两个部分，[1][2][3]（我们可以称之为 A）和 [4][5]< /code>，我们可以称之为B。下面显示的 --> 链接是指向列表中第一个元素的指针。

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

您想要做的是重置链接，以便 A 中的最后一个元素指向 B 中的第一个元素，以及 B 中的最后一个元素> 指向A 中的第一个元素。另外，列表的开头现在是 B 中的第一个元素。

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

所以现在我们只需在需要的地方断开并重置链接即可。

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

• 将列表的开头设置为 B 的第一个元素，即 [4]
• 设置 B 的最后一个元素，即 < code>[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]

从 header 开始，每次我们都可以按这个顺序访问我们的项目时，按照 next 指针遍历列表 [1][2][3][4][5] 。这并不奇怪！

让我们改变一下，因为我们希望 [3] 位于后面。因此，让我们将尾节点设置为指向 [3]。然后沿着[3]的下一个指针我们到达[4]。为此，我们分配 header.So header=[4];tail=[3]

现在从我们的 header 指向的任何内容开始处理我们的列表，我们有 [4][5][1][2][3]。

看起来我们已经执行了移动操作，但我们没有篡改我们的数据结构或其链接 - 只是我们使用它的方式。我们所改变的只是头部和尾部。 （我们的指点）。这就是循环列表的美妙之处。