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

#include <stdio.h>
#include <stdlib.h>
struct node {
    int num;
    struct node* next;
};
int main() {
    int n, i;
    scanf("%d", &n);
    int a[n];
    struct node* head = (struct node*)malloc(sizeof(struct node));
    struct node* p = head;
    for (i = 0; i < n; i++) {//该循环将数组转化为链表
        scanf("%d", &a[i]);
        head->next = (struct node*)malloc(sizeof(struct node));
        head->next->num = a[i];
        head = head->next;
        if (i == n - 1) head->next = NULL;
    }
    head = p;
    if (n == 1 || n == 2) {//如果链表只有一个或两个节点，那么无论交不交换都是一样的，直接输出
        while (p->next) {
            printf("%d ", p->next->num);
            p = p->next;
        }
    } else {//当链表至少有三个节点时，考虑先将前两个节点进行交换，再对最后两个节点进行交换
        struct node* q, *k;//要想交换前两个节点，首先要保存头结点的地址，否则当头指针指向第二个节点的时候，第一个节点的地址就无法得到了，同时也要保存第三个节点的地址，因为当第二个节点的指针指向第一个节点的时候，第三个节点的地址也无法得到了。
        k = head->next; //保存头结点的地址
        q = head->next->next->next; //保存第三个节点的地址
        p->next = p->next->next;
        p->next->next = k;
        p->next->next->next = q;
        while (1) {//对最后两个节点进行交换
            if (p->next->next->next == NULL) {//此条件即为临时指指针向了倒数第三个节点，此时可以对最后两个节点进行交换
                k = p->next; //保存倒数第二个节点的地址，原理同上
                p->next = p->next->next;
                p->next->next = k;
                p->next->next->next = NULL;
                break;
            }
            p = p->next;
        }
        p = head;//让临时指针重新指向一开始的位置，遍历输出交换后的链表即可
        while (p->next) {
            printf("%d ", p->next->num);
            p = p->next;
        }
    }
    return 0;
}