首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >是否有一套通用的指令来交换链表中的相邻和非相邻记录?

问是否有一套通用的指令来交换链表中的相邻和非相邻记录?
EN

Stack Overflow用户
提问于 2020-11-17 05:47:13
回答 1查看 33关注 0票数 1

对于单链表,交换不相邻的单元格可以通过以下操作来描述,假设'=>‘意味着'now links to':

代码语言:javascript
复制
Y => X->next
X => Y->next
BeforeY => X
BeforeX => Y

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

相邻的记录交换,假设X在Y之前,可以用一组单独的操作来描述:

代码语言:javascript
复制
X => Y->next
Y => X
BeforeX => Y

我似乎不能将这组操作作为上一个集合的子集或父集的公共子集来解决。

是否有一组统一的、无条件的操作来描述对相邻和非相邻记录都有效的交换?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-11-17 14:31:52

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

不相邻的X和Y

在列表中,X可以在Y之前或之后,只要X和Y之间至少有一个元素(因此,当X在Y之前时,Ax和By可以标识相同的节点)。之前的情况:

代码语言:javascript
复制
     Bx       X        Ax           By       Y        Ay

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

以下情况:

代码语言:javascript
复制
     Bx       X        Ax           By       Y        Ay
                   +------------------------------+
                   |                              |
          +------------------------------+        |
          |        |                     |        |
   +----+ | +----+ | +----+       +----+ | +----+ | +----+   
   |    |-+ |    |-+ |    |       |    | +>|    | +>|    |
-->|   @|   |   @|   |    |--...->|   @|   |   @|   |    |-->
   |    | +>|    | +>|    |       |    |-+ |    |-+ |    |
   +----+ | +----+ | +----+       +----+ | +----+ | +----+   
          |        |                     |        |
          +------------------------------+        |
                   |                              |
                   +------------------------------+

标有@的4个'next‘指针被更改。

之前:

代码语言:javascript
复制
Bx->next = X
X->next  = Ax
By->next = Y
Y->next  = Ay

之后:

代码语言:javascript
复制
Bx->next = Y
Y->next  = Ax
By->next = X
X->next  = Ay

相邻的X和Y

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

代码语言:javascript
复制
     Bx         X          Ax
                By         Y          Ay

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

以下情况:

代码语言:javascript
复制
     Bx         X          Ax
                By         Y          Ay
                                   
          +------------+
          |            |
   +----+ |   +----+   | +----+     +----+
   |    |-+   |    |   +>|    |     |    |
-->|   @|     |   @|     |   @|     |    |-->
   |    |   +>|    |-+   |    |-+ +>|    |
   +----+   | +----+ |   +----+ | | +----+
            |        |          | |
            +-------------------+ |
                     |            |
                     +------------+

之前:

代码语言:javascript
复制
Bx->next = X
X->next  = Ax = Y
By->next = Y
Y->next  = Ay

之后:

代码语言:javascript
复制
Bx->next = Y
Y->next  = X        # Different
By->next = Ay       # Different
X->next  = Ay

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

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/64866206

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档