单链表首节点与指定节点交换功能实现问题求助

问题描述 #

现有一段C语言代码，意图实现单链表首节点（固定位置1）与另一指定位置节点的交换，但功能无法正常实现。代码核心功能如下：

• 从键盘输入链表节点数量
• 创建链表并输入每个节点的数据
• 输入要交换的两个节点位置（pos1固定为1，pos2为另一节点位置）
• 调用swapFirstNode函数完成交换并显示结果

原代码 #

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

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

Node *createLinkedList(int n);
void displayList(Node *head);
void swapFirstNode(Node *head, int pos1, int pos2);

int main()
{
    int n, pos1, pos2;
    Node *HEAD = NULL;
    printf("\n Enter the number of nodes : ");
    scanf("%d", &n);

    HEAD = createLinkedList(n);
    displayList(HEAD);

    printf("\n Enter first node position to swap : ");
    scanf("%d", &pos1);
    printf("\n Enter second node position to swap : ");
    scanf("%d", &pos2);
    if(pos1 == 1 && pos2 != 1)
        swapFirstNode(HEAD, pos1, pos2);
    displayList(HEAD);
}

Node *createLinkedList(int n)
{
    int i, value;
    Node *head = NULL;
    Node *temp = NULL;
    Node *curr = NULL;

    head = (struct node*)malloc(sizeof(struct node));
    if(head == NULL)
    {
        printf("\n Memory can not be allocated!");
    }
    else
    {
        printf("\n Input data for node 1 : ");
        scanf("%d", &value);
        head->data = value;
        head->next = NULL;
        temp = head;

        for(i=2; i<=n; i++)
        {
            curr = (struct node *)malloc(sizeof(struct node));
            if(curr == NULL)
            {
                printf(" Memory can not be allocated.");
                break;
            }
            else
            {
                printf("\n Input data for node %d : ", i);
                scanf("%d", &value);
                curr->data = value;
                curr->next = NULL;
                temp->next = curr;
                temp = temp->next;
            }
        }
    }
    return head;
}

void displayList(Node *head)
{
    Node *curr = head;
    printf("\n");
    printf(" ");
    while(curr != NULL)
    {
        printf("%d->", curr->data);
        curr = curr->next;
    }
    printf("NULL\n");
}

void swapFirstNode(Node *head, int pos1, int pos2)
{
    Node *curr = head, *node1 = NULL, *node2 = NULL, *prev_node1 = NULL, *prev_node2 = NULL, *temp = NULL;
    int counter = 0, value, i = 1;
    /// Find out how many nodes are in list
    while(curr != NULL)
    {
        counter++;
        curr = curr->next;
    }

    if(pos1 < 1 || pos1 > counter || pos2 < 1 || pos2 > counter)
        exit(0);
    /// Retain the maxim value between two position entered from the keyboard
    value = pos1 > pos2 ? pos1 : pos2;
    curr = head;
    node1 = curr;
    while(curr != NULL && i <= value)
    {
        if(pos2 != 1)
        {
            /// Set the previous node (the node before the second node), regarding the pos2-1
            if(i == (pos2-1))
                prev_node2 = curr;
            /// Set the seconde node, regarding the pos2 entered from the keyboard
            if(i == pos2)
                node2 = curr;
        }
        curr = curr->next;
        i++;
    }
    /// Try to swap the two nodes
    if(node1 != NULL && node2 != NULL)
    {
        if(prev_node2 != NULL)
        {
            temp = head;
            node1->next = node2->next;
            node2 = temp;
            prev_node2->next = node1;
            node2->next = temp->next;
        }
    }
}

问题分析 #

1. 首节点指针无法更新：swapFirstNode函数接收的是Node *head（指针副本），修改副本不会影响main函数中的HEAD指针，导致首节点交换后链表头无法同步更新。
2. 交换逻辑混乱：原代码中node2 = temp仅修改局部指针指向，未实际调整链表连接关系；后续指针赋值逻辑错误，导致链表结构断裂或连接异常。

修复后的代码 #

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

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

Node *createLinkedList(int n);
void displayList(Node *head);
void swapFirstNode(Node **head, int pos1, int pos2);

int main()
{
    int n, pos1, pos2;
    Node *HEAD = NULL;
    printf("\n Enter the number of nodes : ");
    scanf("%d", &n);

    HEAD = createLinkedList(n);
    displayList(HEAD);

    printf("\n Enter first node position to swap : ");
    scanf("%d", &pos1);
    printf("\n Enter second node position to swap : ");
    scanf("%d", &pos2);
    if(pos1 == 1 && pos2 != 1)
        swapFirstNode(&HEAD, pos1, pos2);
    displayList(HEAD);
}

Node *createLinkedList(int n)
{
    int i, value;
    Node *head = NULL;
    Node *temp = NULL;
    Node *curr = NULL;

    head = (struct node*)malloc(sizeof(struct node));
    if(head == NULL)
    {
        printf("\n Memory can not be allocated!");
    }
    else
    {
        printf("\n Input data for node 1 : ");
        scanf("%d", &value);
        head->data = value;
        head->next = NULL;
        temp = head;

        for(i=2; i<=n; i++)
        {
            curr = (struct node *)malloc(sizeof(struct node));
            if(curr == NULL)
            {
                printf(" Memory can not be allocated.");
                break;
            }
            else
            {
                printf("\n Input data for node %d : ", i);
                scanf("%d", &value);
                curr->data = value;
                curr->next = NULL;
                temp->next = curr;
                temp = temp->next;
            }
        }
    }
    return head;
}

void displayList(Node *head)
{
    Node *curr = head;
    printf("\n");
    printf(" ");
    while(curr != NULL)
    {
        printf("%d->", curr->data);
        curr = curr->next;
    }
    printf("NULL\n");
}

void swapFirstNode(Node **head, int pos1, int pos2)
{
    Node *curr = *head, *node1 = *head, *node2 = NULL, *prev_node2 = NULL;
    int counter = 0, i = 1;

    // 统计链表节点总数
    while(curr != NULL)
    {
        counter++;
        curr = curr->next;
    }

    // 位置合法性检查，位置无效或无需交换时直接返回
    if(pos1 < 1 || pos1 > counter || pos2 < 1 || pos2 > counter || pos1 == pos2)
        return;

    curr = *head;
    // 定位目标节点node2及其前驱节点prev_node2
    while(curr != NULL && i <= pos2)
    {
        if(i == pos2 - 1)
            prev_node2 = curr;
        if(i == pos2)
            node2 = curr;
        curr = curr->next;
        i++;
    }

    // 执行交换逻辑
    if(node1 != NULL && node2 != NULL)
    {
        // 让前驱节点指向原首节点
        if(prev_node2 != NULL)
            prev_node2->next = node1;
        // 交换两个节点的后继指针
        Node *temp = node1->next;
        node1->next = node2->next;
        node2->next = temp;
        // 更新链表头为新的首节点node2
        *head = node2;
    }
}

修复说明 #

1. 修改函数参数：将swapFirstNode的参数改为Node **head，通过指针的指针直接修改main函数中的链表头指针，确保首节点交换后链表头正确更新。
2. 简化交换逻辑：
   • 先定位目标节点node2及其前驱节点prev_node2
   • 调整前驱节点的指向，将其连接到原首节点
   • 交换两个节点的后继指针，保持链表连续性
   • 更新链表头为node2，完成首节点替换
3. 优化合法性检查：增加位置相等时直接返回的逻辑，避免无意义操作。

内容的提问来源于stack exchange，提问作者mircead