如何打乱双向链表？

Question

我试图在不改变它的指针的情况下打乱一个双向链表。到目前为止，我的想法是有一个位置整数值，该值被随机分配给双向链表中的每个结构。我想按照位置值分配的顺序来前后遍历双向链表。

假设列表中位置值的顺序为 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);
        }


    }

}

以下是位置值的示例：

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

Answer 1

如果您定义一些函数来创建节点、获取列表的长度以及获取特定索引处的节点，那么这将变得相当简单。

一个简化的示例，每个节点中只有一个 int 和一个单链表，但您应该能够推断出逻辑。警告：这种扩展性很差，因为它是链表的 O(n^2) 算法。对于大样本量，您最好在具有基于索引的恒定时间访问的数组之间进行转换。

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

typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

ListNode *make_node(int val) {
    ListNode *n = malloc(sizeof(*n));
    n->val = val;
    n->next = NULL;

    return n;
}

size_t length(ListNode *n) {
    size_t len = 0;
    for (ListNode *c = n; c; len++) {
        c = c->next;
    }

    return len;
}

ListNode *get_at_idx(ListNode *n, size_t i) {
    ListNode *c = n;
    for (size_t j = 0; c && j < i; j++) 
        c = c->next;

    return c;
}

void shuffle(ListNode *n) {
    size_t len = length(n);
    
    for (size_t i = 0; i < len - 1; i++) {
        ListNode *cur_node = get_at_idx(n, i);

        int rand_idx = rand() % (len - i - 1) + i + 1;

        ListNode *r = get_at_idx(n, rand_idx);

        int temp = r->val;
        r->val = cur_node->val;
        cur_node->val = temp;
    }
}

int main(void) {
    srand(time(NULL));

    ListNode *n = make_node(1);
    n->next = make_node(2);
    n->next->next = make_node(3);
    n->next->next->next = make_node(4);

    shuffle(n);

    for (ListNode *c = n; c; c = c->next) {
        printf("%d\n", c->val);
    }    
}

结果：

% ./a.out                 
3
1
4
2
% ./a.out
4
1
2
3
% ./a.out
2
3
4
1
% ./a.out
3
4
2
1