如何不修改指针实现双向链表洗牌及按position顺序遍历？

需求说明 #

我希望在不修改双向链表指针的前提下实现洗牌操作，思路是给每个链表节点的Record结构体分配唯一的随机position整数值，之后按position从1到n的顺序遍历访问节点。比如链表节点的position值顺序为1,9,8,10,4,5,3,7,6,2，请问怎么遍历才能按1、2、3、4……的顺序访问节点？

结构体定义 #

typedef struct record{
    char artist[50];
    char albumTitle[50];
    char songTitle[50];
    char genre[50];
    Duration songLength;
    int timesPlayed;
    int rating;
    int position;
}Record;

typedef struct node{
    struct node *pPrev;
    struct node *pNext;
    Record record;
}Node;

当前尝试代码 #

void shuffleRecords(Node *pList){
    int recordAmount = countRecords(pList);
    Node *pCurr = pList;
    Record recordArr[recordAmount];
    int assignedPositions[recordAmount];
    int index=0;
    Record tempRecord;

    //initialize assigned positions
    for(int i = 0; i < recordAmount; i++){
        assignedPositions[i] = 0;
    }


    while(pCurr != NULL){
        recordArr[index] = pCurr->record;
        index++;
        pCurr=pCurr->pNext;
    }
    for(int i = 0; i < recordAmount;i++){
        int newPosition;
        do{
            newPosition = rand() % recordAmount + 1;
        }while(assignedPositions[newPosition-1] == 1);
        recordArr[i].position = newPosition;
        assignedPositions[newPosition-1] = 1;
        printf("%s|%s|%s|%s|%d:%d|%d|%d POSITION: %d\n",recordArr[i].artist,recordArr[i].albumTitle,
               recordArr[i].songTitle,recordArr[i].genre,
               recordArr[i].songLength.minutes,recordArr[i].songLength.seconds,
               recordArr[i].timesPlayed,recordArr[i].rating,recordArr[i].position);
    }
    for(int i = 0; i < recordAmount;i++){
        Node *pTraverse=pList;
        int traverseIndex = i+1;
        if(traverseIndex % 2 == 0){//traverse forwards
            while(pTraverse != NULL && pTraverse->record.position != traverseIndex){
                pTraverse=pTraverse->pNext;
            }
        }else{//traverse backwards
            while(pTraverse != NULL && pTraverse->record.position != traverseIndex){
                pTraverse=pTraverse->pPrev;
            }
        }
        if (pTraverse != NULL){
            printf("%s\n",pTraverse->record.songTitle);
        }
    }
}

Position值示例 #

Brooks, Garth|FRESH HORSES|The Old Stuff|Country|2:57|11|2 POSITION: 8
Swift, Taylor|RED|Stay Stay Stay|Pop|4:42|5|1 POSITION: 1
Adele|25|Remedy|Pop|4:11|24|4 POSITION: 4
Eminem|SHADYXV|Vegas|Rap|3:37|8|3 POSITION: 7
Bieber, Justin|PURPOSE|No Sense|Pop|4:12|6|1 POSITION: 5
Perri, Christina|HEAD OF HEART|Trust|Pop|2:35|3|5 POSITION: 3
Drake|YOU WELCOME|The Motto|Rap|4:13|7|4 POSITION: 9
Drake|NOTHING WAS THE SAME|Own it|Rap|3:23|3|3 POSITION: 2
Swift, Taylor|1989|Shake it Off|Pop|3:35|12|3 POSITION: 6

问题分析与解决方案 #

当前代码的问题 #

1. 将Record复制到数组修改position后，没有同步回原链表节点，导致链表节点的position值并未更新，后续遍历找不到对应节点。
2. 奇偶方向遍历的逻辑错误：pList是链表头节点，其pPrev为NULL，反向遍历会直接终止，无法找到目标节点。

正确实现方案 #

要实现按position顺序遍历，最高效的方式是构建position到节点指针的映射，具体步骤如下：

1. 给链表每个节点分配唯一随机position值，直接操作原链表节点，无需复制数组。
2. 创建一个指针数组，将每个节点指针放入数组的position-1索引位置（因为position从1开始）。
3. 按数组索引从0到n-1的顺序访问，即可得到position从1到n的节点序列。

修改后的代码示例 #

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

// 假设countRecords函数已实现，用于统计链表节点数量
int countRecords(Node *pList) {
    int count = 0;
    Node *curr = pList;
    while (curr != NULL) {
        count++;
        curr = curr->pNext;
    }
    return count;
}

void shuffleRecords(Node *pList) {
    int recordAmount = countRecords(pList);
    if (recordAmount == 0) return;

    // 1. 初始化已使用的position标记数组
    int *assignedPositions = calloc(recordAmount, sizeof(int));
    if (assignedPositions == NULL) {
        perror("Failed to allocate memory");
        return;
    }

    // 2. 遍历链表，给每个节点分配唯一随机position
    Node *pCurr = pList;
    while (pCurr != NULL) {
        int newPosition;
        do {
            newPosition = rand() % recordAmount + 1;
        } while (assignedPositions[newPosition - 1] == 1);
        
        pCurr->record.position = newPosition;
        assignedPositions[newPosition - 1] = 1;
        pCurr = pCurr->pNext;
    }

    // 3. 构建position到节点指针的映射数组
    Node **posMap = malloc(recordAmount * sizeof(Node*));
    if (posMap == NULL) {
        perror("Failed to allocate memory");
        free(assignedPositions);
        return;
    }

    pCurr = pList;
    while (pCurr != NULL) {
        int idx = pCurr->record.position - 1;
        posMap[idx] = pCurr;
        pCurr = pCurr->pNext;
    }

    // 4. 按position顺序遍历输出
    printf("按position顺序的歌曲列表：\n");
    for (int i = 0; i < recordAmount; i++) {
        printf("%s\n", posMap[i]->record.songTitle);
    }

    // 释放内存
    free(assignedPositions);
    free(posMap);
}

代码关键点说明 #

• 直接修改链表节点的position值，确保数据同步。
• 用posMap数组实现O(1)的位置查找，整体时间复杂度为O(n)，比每次遍历链表查找的O(n²)高效得多。
• 动态分配内存避免栈溢出（原代码中用栈数组recordArr[recordAmount]，当节点数量大时可能触发栈溢出）。

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