单链表首尾对应位置元素交换功能异常排查求助

问题描述 #

我要实现单链表中开头第k个与结尾第k个元素的交换功能，一开始考虑过双向链表，最终选择单链表方案。思路是：1. 找到链表开头第k个元素；2. 通过链表长度计算找到结尾第k个元素。但运行代码后，程序没完成交换就直接退出，查了很多方案还是找不到问题。

原代码 #

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

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

Node *head = NULL;

void insert();
void display();
void swap();

int main()
{
    int choice;
    while (1)
    {
        printf("\n1.Insert beginning\n");
        printf("2.Display\n");
        printf("3.Swap\n");
        scanf("%d", &choice);
        switch (choice)
        {
          case 1:
            {
                insert();
                break;
            }
          case 2:
            {
                display();
                break;
            }
          case 3:
            {
                swap();
                break;
            }
          default:
            {
                printf("Error!\n");
                return 0;
            }
        }
    }
    return 0;
}

void insert()
{
    Node *current;
    current = (Node *)malloc(sizeof(Node));
    if (current == NULL)
    {
        printf("Out of memory!\n");
        return;
    }
    printf("Enter a value \n");
    scanf("%d", &current->data);
    current->next = NULL;
    if (head == NULL)
    {
        head = current;
    }
    else
    {
        current->next = head;
        head = current;
    }
}

void display()
{
    Node *temp;
    if (head == NULL)
    {
        printf("List is empty!\n");
        return;
    }
    else
    {
        temp = head;
        while (temp != NULL)
        {
            printf("%d ", temp->data);
            temp = temp->next;
        }
    }
}

void swap()
{
    Node *current1, *current2, *prev1, *prev2, *temp;
    temp = NULL;
    int k;
    int n;
    printf("Enter a range: \n");
    scanf("%d", &n);
    printf("Enter a pos: \n");
    scanf("%d", &k);
    prev1 = NULL;
    prev2 = NULL;
    current1 = head;

    for (int i = 0; i < n; ++i)
    {
        current1 = current1->next;
        if (i == k)
        {
            prev1 = current1;
        }
    }
    current2 = head;
    for (int i = 0; i < n - k - 1; ++i)
    {
        prev2 = current2;
        current2 = current2->next;
    }

    prev1->next = current2;
    prev2->next = current1;

    temp = current1->next;
    current1->next = current2->next;
    current2->next = temp;
}

错误分析 #

1. 循环逻辑完全错误：原swap函数中找开头第k个节点的循环执行了n次，最终current1会变成NULL，且prev1的赋值逻辑完全搞错了目标节点与前驱的关系，直接导致空指针访问，程序崩溃退出。
2. 依赖用户输入链表长度：用户输入的n可能与实际链表长度不符，引发越界访问。
3. 未处理边界情况：当交换节点是头节点/尾节点，或两个交换节点为同一个时，直接访问prev->next会触发空指针错误。
4. 缺失输入验证：未检查k的合法性（如k<0、k>=n/2等），非法输入会导致逻辑混乱。

修正方案 #

1. 新增计算链表长度的函数，自动获取长度，无需用户输入。
2. 正确定位目标节点及其前驱。
3. 处理所有边界场景，避免空指针访问。
4. 增加输入合法性校验。

修正后的完整代码 #

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

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

Node *head = NULL;

void insert();
void display();
void swap();
int getLength();

int main()
{
    int choice;
    while (1)
    {
        printf("\n1.Insert beginning\n");
        printf("2.Display\n");
        printf("3.Swap\n");
        printf("4.Exit\n");
        scanf("%d", &choice);
        switch (choice)
        {
          case 1:
            insert();
            break;
          case 2:
            display();
            break;
          case 3:
            swap();
            break;
          case 4:
            printf("Exit program\n");
            return 0;
          default:
            printf("Invalid choice!\n");
            break;
        }
    }
    return 0;
}

void insert()
{
    Node *current;
    current = (Node *)malloc(sizeof(Node));
    if (current == NULL)
    {
        printf("Out of memory!\n");
        return;
    }
    printf("Enter a value: \n");
    scanf("%d", &current->data);
    current->next = NULL;
    if (head == NULL)
    {
        head = current;
    }
    else
    {
        current->next = head;
        head = current;
    }
}

void display()
{
    Node *temp;
    if (head == NULL)
    {
        printf("List is empty!\n");
        return;
    }
    temp = head;
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int getLength()
{
    int len = 0;
    Node *temp = head;
    while (temp != NULL)
    {
        len++;
        temp = temp->next;
    }
    return len;
}

void swap()
{
    int k;
    int n = getLength();
    if (n == 0)
    {
        printf("List is empty!\n");
        return;
    }
    printf("Enter position k (0-based): \n");
    scanf("%d", &k);

    // 验证k的合法性：k不能是负数，且开头第k个和结尾第k个不能是同一个节点
    if (k < 0 || k >= n/2)
    {
        printf("Invalid position k!\n");
        return;
    }

    Node *node1, *node2, *prev1, *prev2;
    prev1 = NULL;
    node1 = head;
    // 找到开头第k个节点（索引k）及其前驱
    for (int i = 0; i < k; i++)
    {
        prev1 = node1;
        node1 = node1->next;
    }

    prev2 = NULL;
    node2 = head;
    // 找到结尾第k个节点，即正数第n-k-1个节点
    for (int i = 0; i < n - k - 1; i++)
    {
        prev2 = node2;
        node2 = node2->next;
    }

    // 如果两个节点是同一个，无需交换
    if (node1 == node2)
        return;

    // 处理前驱指针
    if (prev1 == NULL)
    {
        // node1是头节点，更新head为node2
        head = node2;
    }
    else
    {
        prev1->next = node2;
    }

    if (prev2 == NULL)
    {
        // node2是头节点，更新head为node1
        head = node1;
    }
    else
    {
        prev2->next = node1;
    }

    // 交换两个节点的next指针
    Node *temp = node1->next;
    node1->next = node2->next;
    node2->next = temp;

    printf("Swap completed!\n");
}

测试示例 #

按照需求依次插入10、9、8、...、1（display时顺序为1 2 3 ... 10），输入k=3：

• 原链表：1 2 3 4 5 6 7 8 9 10
• 交换后：1 2 3 7 5 6 4 8 9 10，与预期一致。

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