题解 | 牛牛的链表交换

#include <stdio.h>
#include <stdlib.h>
#define N 100

struct Node
{
    int data;
    struct Node *next;
};

struct Node* createList(int arr[],int n)
{
    struct Node *head = NULL, *tail = NULL;
    for(int i = 0; i < n; i++)
    {
        struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));//为新创建的指针分配内存
        newNode -> data = arr[i];
        newNode -> next = NULL;

        if(head == NULL)
        {
            head = newNode;
            tail = newNode;
        }
        else {
        tail -> next = newNode;
        tail = newNode;
        }
    }
    return head;
}

//交换链表前两个节点
//操作：想要交换链表的前两个节点，就是需要让原链表的表头指向节点3，让原链表的节点2指向表头；
struct Node* swapFirstTwo(struct Node *head)
{
    if(head == NULL || head -> next == NULL)
    {
        return head;
    }
    struct Node *second = head -> next;//定义存放了节点2的内存地址的指针变量，该变量指向节点2
    head -> next = second -> next;//让头指针的下一个节点指向原本节点2的下一个节点（即节点3）：将原本的头指针放到原本节点2的位置；
    second -> next = head;//使原来节点2成为新的表头
    return second;
}

//交换链表最后两个节点
void swapLastTwo(struct Node *head)
{
    if(head == NULL || head -> next == NULL)
    {
        return;
    }
    struct Node *p = head;
    //找到倒数第二个节点
    while(p -> next -> next != NULL)
    {
        p = p -> next;
    }
    // 交换倒数第二个和最后一个节点
    struct Node *last = p -> next;
    p -> next = NULL;// 原倒数第二个节点变为最后一个
    last -> next = p;// 原最后一个节点指向原倒数第二个
      // 找到倒数第三个节点，让其指向新的倒数第二个节点
      struct Node *q = head;
      if(q != p)
      {
        while(q -> next != p)
        {
            q = q -> next;
        }
        q -> next = last;
      }
}
void printList(struct Node *head)
{
    struct Node *p = head;
    while(p != NULL)
    {
        printf("%d ",p -> data);
        p = p -> next;
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    int arr[N];
    for(int *p = arr; p < arr + n; p++)
    {
        scanf("%d",p);
    }

    struct Node *head = createList(arr,n);
    if(n >= 2)
    {
        head = swapFirstTwo(head);
        swapLastTwo(head);
    }

    printList(head);

    return 0;
}