时间戳

首页 > 解决方案 > 双向链表交换解释

list - 双向链表交换解释

问题描述

'编写一个程序来交换双向链表的前两个节点。

有人可以用图像解释这件事吗？

void swapFirstTwo() {
if (head != tail) {
DLLNode neck = head.next;
head.next = neck.next;
neck.next = head;
head.prev = neck;
neck.prev = null;
if (tail == neck) // two element list
tail = head;
head = neck;
}
}

标签： listalgorithmsortingdata-structuresswap

解决方案

示例-1

1<=>2<=>3->空

结构体-

1.next = 2;2.next = 3;3.next = null; 1.prev = null;2.prev = 1;3.prev = 2;

交换前两个元素意味着交换它们的位置。因此，一旦交换完成，列表将如下所示 - 2<=>1<=>3->null

这就是您粘贴的代码给出预期结果的方式 -

脖子=头。下一个；颈部 = 2;

脖子。下一个=头；2.下一个 = 1;

head.prev = 脖子；1.prev = 2;

head.next = 颈部.next; 1.下一个= 3；

颈部.prev = null; 2.prev = null;

基本上，交换 1 和 2 的 next 和 prev 指针。将上述所有步骤加起来，您会得到-

2.next = 1;1.next = 3;3.next = null 2.prev=null;1.prev = 2;3.prev = 2;

但是上述逻辑中缺少的一步是头部应该指向颈部。因为，交换元素时头部会发生变化。

示例 2

如果列表中只有一个元素，则无需交换

示例 3

如果只有两个元素，除了更改头的指针外，由于维护了列表的尾（尾），您将更新尾，并且尾在交换后将指向当前头，而不是它应该指向当前的脖子。

推荐阅读