题解 | 牛牛的链表交换

#include <stdio.h>
#include <stdlib.h>
int main() {

    int n;
    scanf("%d", &n);

    int* arr = (int*)malloc(n * sizeof(int));

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // write your code here......
    struct ListNode {
        int data;
        struct ListNode* next;
    };
    struct ListNode* head = (struct ListNode*)malloc(sizeof(
                                struct ListNode));//定义指向头节点的指针；
    head->next = NULL;
    struct ListNode* p;//遍历链表的指针;
    struct ListNode* newnode; //定义新节点；
    int* arrptr = arr;//遍历数组的指针；

    for (int i = 0; i < n; i++) {
        //接下来给新节点分配动态内存；
        newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
        //malloc的作用是在堆上分配指定大小的内存，并返回指向这块指针的内存（分配失败则返回NULL）；
        newnode->data = *arrptr;//给新节点的数据域赋初值；
        newnode->next =
            NULL;//给新节点的指针域赋初值，指针必须赋初值；

        //尾插法：将新节点插入链表尾端；
        p = head;//遍历指针从头指针开始遍历；
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = newnode;//找到tail，此时p指向最后一个节点，让最后一个节点后再接新节点；
        arrptr++;
    }

    //链表构建完成，接下来交换；
    struct ListNode* swapptr;
    swapptr = head;
    struct ListNode* first = head->next;
    struct ListNode* second = head->next->next;
    head->next = second;
    first->next = second->next;
    second->next = first;//交换第一个和第二个数据；
    while (swapptr->next->next->next != NULL) {
        swapptr = swapptr->next;
    }//此时swapptr指向倒数第三个节点；
    struct ListNode* last3 = swapptr;
    struct ListNode* last2 = last3->next;
    struct ListNode* last1 = last3->next->next;
    last3->next = last1;
    last1->next = last2;
    last2->next = NULL;//避免形成野指针；
    //交换倒数第二个和倒数第一个节点；
    swapptr = head->next;
    while (swapptr != NULL) {
        printf("%d ", swapptr->data);
        swapptr = swapptr->next;
    }

    //释放所有内存
    struct ListNode* q;
    p = head;
    while (p != NULL) {
        q = p->next;
        free(p);
        p = q;
    }

    free(arr);
    return 0;
}