双链表交换元素

前言

双链表和单链表的插入，删除，交换。可以想象成锁链，但是，前后的链不能断开联系

交换

void SwapWithNextAndLast(Position BeforeP)
{
    Position P = BeforeP->next;
    Position AfterP = P->next;

    P->next = AfterP->next;
    BeforeP->next = AfterP;
    AfterP->next = P;
    P->next->last = P;//注意这行！不能用AfterP->last，因为P和AfterP的位置改变
    P->last = AfterP;
    AfterP->last = BeforeP;
}

插入

*只要把S指针与前后相连，S->next，S->prior与前后指针相连。*就完成了。

• 主要方法

1. 把S的prior,next搞定
2. 再将After的prior与S连上，为了不断线
3. 最后，切断Before的next与After的联系，与S连上

S->prior = P;
S->next = P->next;
P->next->prior = S;
P->next = S;

示例

双链表的实现和交换元素

#include<stdio.h>
#include<stdlib.h>
typedef struct Node * PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
void SwapWithNextAndLast(Position BeforeP);
void PrintTail(List T);

struct Node 
{
    int e;
    Position last;
    Position next;
};
int main()
{
    List L = NULL, T;
    //初始化prev = NULL是为了满足结束条件
    Position prev = NULL, current;

    int n = 0;
    while (n < 4)
    {
        current = (PtrToNode)malloc(sizeof(struct Node));
        if(L == NULL)
            L = current;
        else
            prev->next = current;
        current->last = prev;
        current->next = NULL;
        current->e = n++;

        prev = current;
    }
    //最后一步让T指向最后的一个结构
    T = prev;

    PrintTail(T);
    SwapWithNextAndLast(L);
    PrintTail(T);
    return 0;
}

void SwapWithNextAndLast(Position BeforeP)
{
    Position P = BeforeP->next;
    Position AfterP = P->next;

    P->next = AfterP->next;
    BeforeP->next = AfterP;
    AfterP->next = P;
    P->next->last = P;//注意这行，不能用AfterP，因为要将P的位置改变
    P->last = AfterP;
    AfterP->last = BeforeP;
}

void PrintTail(List T)
{
    while (T != NULL)
    {
        printf("%d ", T->e);
        T = T->last;
    }
    printf("\n");
}