对于单链表,交换不相邻的单元格可以通过以下操作来描述,假设'=>‘意味着'now links to':
Y => X->next
X => Y->next
BeforeY => X
BeforeX => Y但是,此操作不适用于交换相邻记录、创建循环链接,因为X->next (比方说)将是Y。
相邻的记录交换,假设X在Y之前,可以用一组单独的操作来描述:
X => Y->next
Y => X
BeforeX => Y我似乎不能将这组操作作为上一个集合的子集或父集的公共子集来解决。
是否有一组统一的、无条件的操作来描述对相邻和非相邻记录都有效的交换?
发布于 2020-11-17 14:31:52
以下是这两种情况下的一些ASCII艺术。
不相邻的X和Y
在列表中,X可以在Y之前或之后,只要X和Y之间至少有一个元素(因此,当X在Y之前时,Ax和By可以标识相同的节点)。之前的情况:
Bx X Ax By Y Ay
+----+ +----+ +----+ +----+ +----+ +----+
| | | | | | | | | | | |
-->| |-->| |-->| |--...->| |-->| |-->| |-->
| | | | | | | | | | | |
+----+ +----+ +----+ +----+ +----+ +----+ 以下情况:
Bx X Ax By Y Ay
+------------------------------+
| |
+------------------------------+ |
| | | |
+----+ | +----+ | +----+ +----+ | +----+ | +----+
| |-+ | |-+ | | | | +>| | +>| |
-->| @| | @| | |--...->| @| | @| | |-->
| | +>| | +>| | | |-+ | |-+ | |
+----+ | +----+ | +----+ +----+ | +----+ | +----+
| | | |
+------------------------------+ |
| |
+------------------------------+标有@的4个'next‘指针被更改。
之前:
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”的情况-指针旋转必须不同。
https://stackoverflow.com/questions/64866206
复制相似问题