题解 | #牛牛的链表交换#

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* pNext;
} NODE, * PNODE;

PNODE create_list(void);
void traverse_list(PNODE pHead);
void exchange_list(PNODE pHead);

int main() {
    PNODE pHead = NULL;
    pHead = create_list();
    exchange_list(pHead);
    traverse_list(pHead);
    return 0;
}
PNODE create_list(void) {
    int val, n;
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (NULL == pHead) {
        exit(-1);
    }
    PNODE p = pHead;
    p->pNext = NULL;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if (NULL == pNew) {
            exit(-1);
        }
        scanf("%d", &val);
        pNew->data = val;
        pNew->pNext = NULL;
        p->pNext = pNew;
        p = pNew;
    }
    return pHead;
}

void traverse_list(PNODE pHead) {
    PNODE p = pHead->pNext;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->pNext;
    }
    return;
}

void exchange_list(PNODE pHead) {
    PNODE p1 = pHead->pNext;//第一个节点
    PNODE p2 = p1->pNext;//第二个节点
    //前两个节点交换
    p1->pNext = p2->pNext;
    p2->pNext = p1;
    pHead->pNext = p2;

    PNODE pT = NULL;
    PNODE pT1 = NULL;
    PNODE pT2 = NULL;
    for (pT = pHead; pT->pNext->pNext->pNext != NULL;
            pT = pT->pNext);//找到倒数第三个节点
    for (pT1 = pHead; pT1->pNext->pNext != NULL; pT1 = pT1->pNext);//倒数第二个
    for (pT2 = pHead; pT2->pNext != NULL; pT2 = pT2->pNext);//最后一个节点
    //后两个节点交换
    pT1->pNext = NULL;
    pT2->pNext = pT1;
    pT->pNext = pT2;
}