双向链表实现节点的交换_双链表交换两个节点

交换双向链表中的任意两个节点

什么是真正有效的指针？

考虑如下情况：

已知 node1 和 node2 的位置
假设当前二者位置情况是这样的：
[pre1] - [node1] - [be1] - [pre2] - [node2] - [be2]
注意， pre1 和 be2 可能为空指针。因为node1,node2的位置已知，所以我们不需要这两个的前驱或者后继的节点来找到这两个节点，所以凡是指向这两个节点的指针都是无效的，相反，这两个节点的指针所指向的节点都是自身没有名牌的，所以凡是这两个节点指出去的指针都是有效的。有一个很简单的方法判断指针是否为有效指针——改变这个指针的指向，还能否确定原指向的位置，如果能，则该指针为无效指针，否则，为有效指针。显然，node1 和 node2 如果不指向他们的前驱和后继的话，我们就无法确定他们的前驱和后继的位置，然而断开前驱和后继指向node1和node2的指针，我们任然可以知道node1和node2。

既然node1和node2的前驱和后继的指向是无效的，所以应该最先改变这些指针，最后改变node1和node2指出去的指针

这样就有如下思路：

• 改变两个前驱pre1和pre2的next指针的指向
• 改变两个后继be1和be2的prev指针的指向
• 当要改变node1和node2的指针时，我们需要额外备份一个前驱和后继的位置，这里以备份pre1、be1为例
• pre1备份之后，指向它的指针（即node1->prev）无效，可以改变这个指针指向node2的前驱，同时改变node2->prev指向pre1
• 同理，改变二者指向的后继的指针

注意事项：

• node1和node2可能相邻，这种情况要单独处理；
• 前驱和后继可能为空，需要在改变他们的指针的时候判断本身是否为空；

样例代码

    // 为简单，这里备份了所有的前驱和后继
    Job* pre1 = cur1 -> prev;
    Job* pre2 = cur2 -> prev;
    
    Job* be1 = cur1 -> next;
    Job* be2 = cur2 -> next;
    
    // 改变节点1的前驱和后继的指针的指向
    if(pre1)
        pre1 -> next = cur2;
    if(be1)
    be1 -> prev = cur2;
    
    // 改变节点2的前驱和后继的指针的指向
    if(pre2)
        pre2 -> next = cur1;
    if(be2)
    be2 -> prev = cur1;
    
    // 最后改变节点1和节点2的指针
    cur1 -> prev = pre2;
    cur1 -> next = be2;
    
    cur2 -> prev = pre1;
    cur2 -> next = be1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25