如何用C语言按指定规则将单链表转换为交错链表？

转换规则 #

将单链表按以下规则转换为交错链表，每步操作后将当前节点加入结果链表：

1. 从表头开始，先加入表头节点
2. 向前走两步，加入当前节点
3. 向后退一步，加入当前节点
4. 向前走三步，加入当前节点
5. 若未超出链表范围，则回到步骤3重复执行
6. 遍历结束后，若有未访问的剩余元素，全部追加到结果末尾

示例 #

• 奇数个元素：输入 0->1->2->3->4->5->6->7->8->NULL，输出 0->2->1->4->3->6->5->8->7->NULL
• 偶数个元素：输入 0->1->2->3->4->5->6->7->NULL，输出 0->2->1->4->3->6->5->7->NULL
• 特殊情况：
  • 1个或2个元素直接返回原链表
  • 3个元素输入 0->1->2->NULL，输出 0->2->1->NULL

原代码存在的问题 #

你提供的代码无法适配所有用例，核心问题包括：

• 指针初始化错误：fast='\0' 应该用 NULL 初始化指针
• 循环逻辑失效：else 块中的 while(fast) 循环，由于fast初始为NULL，循环根本不会执行
• 硬编码步骤：仅尝试处理前几步，没有实现步骤3到步骤5的循环逻辑
• 未处理剩余未访问元素：没有遍历完所有节点的逻辑

修正后的代码 #

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

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

// 创建链表辅助函数（用于测试）
struct Node* createList(int arr[], int size) {
    if (size == 0) return NULL;
    struct Node *head = (struct Node*)malloc(sizeof(struct Node));
    head->val = arr[0];
    head->next = NULL;
    struct Node *curr = head;
    for (int i = 1; i < size; i++) {
        struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->val = arr[i];
        newNode->next = NULL;
        curr->next = newNode;
        curr = newNode;
    }
    return head;
}

// 释放链表辅助函数
void freeList(struct Node *head) {
    struct Node *temp;
    while (head) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

// 实现交错转换并打印结果
void stagger(struct Node *head) {
    if (head == NULL) {
        printf("NULL\n");
        return;
    }

    // 处理特殊情况：1个或2个元素直接打印
    if (head->next == NULL || head->next->next == NULL) {
        struct Node *curr = head;
        while (curr) {
            printf("%d->", curr->val);
            curr = curr->next;
        }
        printf("NULL\n");
        return;
    }

    // 统计链表长度，方便跟踪已访问节点
    int len = 0;
    struct Node *curr = head;
    while (curr) {
        len++;
        curr = curr->next;
    }

    // 用数组标记已访问节点（索引对应节点位置）
    int *visited = (int*)calloc(len, sizeof(int));
    if (visited == NULL) {
        printf("内存分配失败\n");
        return;
    }

    curr = head;
    int pos = 0; // 当前节点的位置索引
    // 步骤1：加入表头节点
    printf("%d->", curr->val);
    visited[pos] = 1;

    // 步骤2：向前走两步
    for (int i = 0; i < 2 && curr; i++) {
        curr = curr->next;
        pos++;
    }
    if (curr && !visited[pos]) {
        printf("%d->", curr->val);
        visited[pos] = 1;
    }

    // 步骤3-5：循环执行后退一步、前进三步，直到超出链表
    while (1) {
        // 步骤3：向后退一步
        if (pos > 0) {
            // 从表头重新定位到后退后的位置（单链表无法直接后退）
            curr = head;
            pos--;
            for (int i = 0; i < pos; i++) {
                curr = curr->next;
            }
            if (!visited[pos]) {
                printf("%d->", curr->val);
                visited[pos] = 1;
            }
        } else {
            break; // 无法后退，退出循环
        }

        // 步骤4：向前走三步
        int step = 3;
        int newPos = pos;
        while (step-- && curr) {
            curr = curr->next;
            newPos++;
        }
        if (!curr) {
            break; // 超出链表，退出循环
        }
        pos = newPos;
        if (!visited[pos]) {
            printf("%d->", curr->val);
            visited[pos] = 1;
        }
    }

    // 步骤6：追加未访问的剩余元素
    curr = head;
    pos = 0;
    while (curr) {
        if (!visited[pos]) {
            printf("%d->", curr->val);
        }
        curr = curr->next;
        pos++;
    }

    printf("NULL\n");
    free(visited);
}

// 测试函数
int main() {
    // 测试示例1：奇数个元素
    int arr1[] = {0,1,2,3,4,5,6,7,8};
    struct Node *list1 = createList(arr1, 9);
    printf("示例1输出：");
    stagger(list1);
    freeList(list1);

    // 测试示例2：偶数个元素
    int arr2[] = {0,1,2,3,4,5,6,7};
    struct Node *list2 = createList(arr2, 8);
    printf("示例2输出：");
    stagger(list2);
    freeList(list2);

    // 测试特殊情况：3个元素
    int arr3[] = {0,1,2};
    struct Node *list3 = createList(arr3, 3);
    printf("3元素示例输出：");
    stagger(list3);
    freeList(list3);

    // 测试特殊情况：1个元素
    int arr4[] = {5};
    struct Node *list4 = createList(arr4, 1);
    printf("1元素示例输出：");
    stagger(list4);
    freeList(list4);

    return 0;
}

代码说明 #

1. 先处理特殊情况：空链表、1个或2个元素直接返回
2. 统计链表长度并创建访问标记数组，避免重复访问节点
3. 严格按照转换规则分步执行指针移动，由于单链表无法直接后退，通过重新遍历的方式定位后退后的节点
4. 最后遍历链表，追加所有未被访问过的节点
5. 加入了链表创建、释放的辅助函数，方便测试不同用例

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