Java 中的双向链表

Question

我是 IT 专业的新生，我们做了一个关于链表的测验，其中一个问题基本上是重新排列双向链接图。

我得到的答案是“agortihm”，但它被认为是不正确的。。我已经研究了两个小时了，但我仍然不明白他们是如何得出正确答案的。我不断地找到“agotihm”作为答案。任何帮助将不胜感激，谢谢！

Answer 1

前六个语句将节点“i”移动到节点“t”之后。我们从：

开始

               p1                          p2     p3
               ↓                           ↓      ↓
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼─►││i│┼─►││t│┼─►││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘

（a）之后

p2.next.prev = p2.prev;

：

               p1                          p2     p3
               ↓                           ↓      ↓
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼─►││i│┼─►││t│┼─►││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││ ┌┼│ ││◄─┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘ │└┴─┴┘  └┴─┴┘  └┴─┴┘
                                    ▲          │
                                    └──────────┘  

（b）之后

p2.prev.next = p2.next;

：

                                           p2     p3
               p1                      ┌──────────┐
               ↓                       │   ↓      ▼
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐│ ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼┘ ││i│┼─►││t│┼─►││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││ ┌┼│ ││◄─┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘ │└┴─┴┘  └┴─┴┘  └┴─┴┘
                                    ▲          │
                                    └──────────┘  

（c）之后

p2.next = p3.next;

：

                                                  p3
                                       ┌──────────┐
               p1                      │   p2 ┌───│──────┐
               ↓                       │   ↓  │   ▼      ▼
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐│ ┌┬─┬┐│ ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼┘ ││i│┼┘ ││t│┼─►││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││ ┌┼│ ││◄─┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘ │└┴─┴┘  └┴─┴┘  └┴─┴┘
                                    ▲          │
                                    └──────────┘  

（d）之后

p3.next.prev = p2;

：

                                                  p3
                                       ┌──────────┐
               p1                      │   p2 ┌───│──────┐
               ↓                       │   ↓  │   ▼      ▼
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐│ ┌┬─┬┐│ ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼┘ ││i│┼┘ ││t│┼─►││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││ ┌┼│ ││ ┌┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘ │└┴─┴┘ │└┴─┴┘  └┴─┴┘
                                    ▲      ▲   │      │
                                    │      └───│──────┘
                                    └──────────┘  

（e）之后

p3.next = p2;

：

                                           p2     p3
                                           ┌─────────┐
                                       ┌──────────┐  │
               p1                      │   │  ┌───│──────┐
               ↓                       │   ▼  │   ▼  │   ▼
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐│ ┌┬─┬┐│ ┌┬─┬┐│ ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼┘ ││i│┼┘ ││t│┼┘ ││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││ ┌┼│ ││ ┌┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘ │└┴─┴┘ │└┴─┴┘  └┴─┴┘
                                    ▲      ▲   │      │
                                    │      └───│──────┘
                                    └──────────┘  

（f）之后

p2.prev = p3;

：

                                           p2     p3
                                           ┌─────────┐
                                       ┌──────────┐  │
               p1                      │   │  ┌───│──────┐
               ↓                       │   ▼  │   ▼  │   ▼
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐│ ┌┬─┬┐│ ┌┬─┬┐│ ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼┘ ││i│┼┘ ││t│┼┘ ││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││ ┌┼│ ││ ┌┼│ ││ ┌┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘ │└┴─┴┘ │└┴─┴┘ │└┴─┴┘  └┴─┴┘
                                    ▲   │  ▲   │  ▲   │
                                    │   │  └───│──│───┘
                                    └───│──────┘  │
                                        └─────────┘

节点“i”的移动已经完成。当我们将节点“i”描绘在节点“t”的右侧时，我们可以简化上面的绘图。由于这些节点由

p2

和

p3

引用，因此这些节点也会随之移动：

               p1                          p3     p2
               ↓                           ↓      ↓
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼─►││t│┼─►││i│┼─►││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘

接下来的语句不会更改任何内容，因为它们分配目标属性在分配发生之前已经拥有的引用：

list.next.next = p1.next;
p1.next.prev = list.next;

最后一个赋值

p1 = null;

仅影响变量，而不影响列表：

               p1→Ω                        p3     p2
                                           ↓      ↓
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼─►││t│┼─►││i│┼─►││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘

所以结果是：“algortihm”。