交换双向链表中的一组节点
交换双向链表中的一组节点
提问于 2020-11-28 05:25:30
我遇到了这个问题，在这个问题中，您应该交换双向链表中的一组节点。例如:对于列表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连接，但由于这是一个双向链表，我发现很难想出一个解决方案来成功地更改所有需要的指针。有没有人能帮我解释一下该怎么做？谢谢。
回答 2
Stack Overflow用户
发布于 2020-11-28 05:49:40
双向链表中的节点有2个指针：-next元素-previous元素
您应该复制两个间隔的第一个和最后一个元素的指针
-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)Stack Overflow用户
发布于 2020-11-28 06:16:12
双向链表有head和tail。此外，每个节点都有prev和next指针，如果节点分别为head或tail，则指针为null。
我们在这里假设要交换的两个段(start1-end1)和(start2-end2)不重叠。
将所有prev和next引用复制到temp变量
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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/65043992
复制相关文章
相似问题
腾讯云开发者
