是否有一组通用指令来交换单链表中的相邻和不相邻记录？

Question

对于单链表，交换不相邻的单元格可以通过以下操作来描述，假设“=>”表示“现在链接到”：

Y => X->next
X => Y->next
BeforeY => X
BeforeX => Y

但是，此操作不适用于交换相邻记录、创建循环链接，因为 X->next（比如说）将是 Y。

相邻记录交换，假设 X 在 Y 之前，可以通过一组单独的操作来描述：

X => Y->next
Y => X
BeforeX => Y

我似乎无法将这组操作作为前一组操作的子集或父组的公共子组来解决。

是否存在一组统一的、无条件的操作来描述适用于相邻和非相邻记录的交换？

Answer 1

这是这两种情况的一些 ASCII 艺术。

X 和 Y 不相邻

X 可以在列表中位于 Y 之前或之后，只要 X 和 Y 之间至少有一个元素（因此当 X 位于 Y 之前时，Ax 和 By 可以识别相同的节点）。 之前的情况：

     Bx       X        Ax           By       Y        Ay

   +----+   +----+   +----+       +----+   +----+   +----+   
   |    |   |    |   |    |       |    |   |    |   |    |   
-->|    |-->|    |-->|    |--...->|    |-->|    |-->|    |-->
   |    |   |    |   |    |       |    |   |    |   |    |   
   +----+   +----+   +----+       +----+   +----+   +----+   

之后的情况：

     Bx       X        Ax           By       Y        Ay
                   +------------------------------+
                   |                              |
          +------------------------------+        |
          |        |                     |        |
   +----+ | +----+ | +----+       +----+ | +----+ | +----+   
   |    |-+ |    |-+ |    |       |    | +>|    | +>|    |
-->|   @|   |   @|   |    |--...->|   @|   |   @|   |    |-->
   |    | +>|    | +>|    |       |    |-+ |    |-+ |    |
   +----+ | +----+ | +----+       +----+ | +----+ | +----+   
          |        |                     |        |
          +------------------------------+        |
                   |                              |
                   +------------------------------+

标有

@

的 4 个“下一个”指针已更改。

之前：

Bx->next = X
X->next  = Ax
By->next = Y
Y->next  = Ay

之后：

Bx->next = Y
Y->next  = Ax
By->next = X
X->next  = Ay

相邻的 X 和 Y

假设X紧接在Y之前。之前的情况：

     Bx         X          Ax
                By         Y          Ay

   +----+     +----+     +----+     +----+
   |    |     |    |     |    |     |    |
-->|    |---->|    |---->|    |---->|    |-->
   |    |     |    |     |    |     |    |
   +----+     +----+     +----+     +----+

之后的情况：

     Bx         X          Ax
                By         Y          Ay
                                   
          +------------+
          |            |
   +----+ |   +----+   | +----+     +----+
   |    |-+   |    |   +>|    |     |    |
-->|   @|     |   @|     |   @|     |    |-->
   |    |   +>|    |-+   |    |-+ +>|    |
   +----+   | +----+ |   +----+ | | +----+
            |        |          | |
            +-------------------+ |
                     |            |
                     +------------+

之前：

Bx->next = X
X->next  = Ax = Y
By->next = Y
Y->next  = Ay

之后：

Bx->next = Y
Y->next  = X        # Different
By->next = Ay       # Different
X->next  = Ay

指针中的结果值不同，如图所示。 这意味着没有一个映射可以同时适用于“不相邻的 X 和 Y”和“相邻的 X 和 Y”情况 - 指针旋转必须不同。