java—交换双链表中的一组节点

d4so4syb 于 2021-07-08 发布在 Java

关注(0)|答案(2)|浏览(292)

我遇到了一个问题，在这个问题中，您应该交换一组双链表中的节点。例如：对于列表 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8 对于给定的间隔2-4和6-7，您应该将间隔中的节点作为一个组与间隔中的其他节点交换，以获得输出 1 <-> 6 <-> 7 <-> 5 <-> 2 <-> 3 <-> 4 <-> 8 . 我的想法是将整个组视为一个节点，这意味着我应该将6.prev与1连接起来，将7.next与5连接起来，但是由于这是一个双链接列表，我发现很难想出一个能够成功更改所有所需指针的解决方案。有人能帮我解释一下怎么做吗？谢谢。

Java Algorithm doubly-linked-list

来源：https://stackoverflow.com/questions/65043992/swap-group-of-nodes-in-a-doubly-linked-list

2条答案

按热度按时间

k5ifujac1#

双链表中的“节点”有2个指针：-下一个元素-上一个元素
应该复制两个间隔的第一个和最后一个元素的指针

-First1,Last1 = 2,4 //(i mean the pointer to 2 and 4 not integer)
-First2,Last2 = 6,7

作为交换间隔的最终操作，您应该说

(First2.previous).next = First1  // ( First2.previous is 5 in the example)
(Next2.next).previous = Next1   // (Next2.next is 8 in the example)

(First1.previous).next = First2 //(First1.previous is 1)
(Next1.next).previous = Next2   //(Next1.next is 5)

赞(0）回复(0）举报 2021-07-09

pvabu6sv2#

双链表 head 以及 tail . 每个节点也有 prev 以及 next 指针是 null 如果节点是 head 或者 tail 分别。
我们在这里的假设是，有两段要交换 (start1-end1) 以及 (start2-end2) 没有重叠。
全部复制 prev 以及 next 对临时变量的引用

1. prev1=start1.prev, prev2=start2.prev, next1=end1.next, next2=end2.next

互换 start1 以及 start2 ，并处理条件，如果 start1 是 head ```
2. start2.prev=prev1
3. if prev1=null, head=start2 else prev1.next=start2
4. start1.prev=prev2
5. prev2.next=start1

互换 `end1` 以及 `end2` ，并处理条件，如果 `end2` 是 `tail` ```
6. end1.next=next2
7. if next2=null, tail=end1 else next2.prev=end1
8. end2.next=next1
9. next1.prev=end2

赞(0）回复(0）举报 2021-07-09

我来回答

java—交换双链表中的一组节点

2条答案

相关问题

热门标签

最新问答