链接列表伪代码可以在CLRS算法介绍中找到 ，但是如果您非常想要，我可以将其重写为链接列表的演示
Linked List pseudocode can be found in CLRS introduction to the algorithms but if you want it very much i can rewrite it as demo of the linked list
//node structure struct node { int key; struct node *next; struct node *prev; }; typedef struct node node; void split(node *head,node **front,node **back) { node *slow,*fast; if(head == NULL || head->next == NULL) { (*front) = head; (*back) = NULL; } else { slow = head; fast = head->next; while(fast != NULL) { fast = fast->next; if(fast != NULL) { slow = slow->next; fast = fast->next; } } (*front) = head; (*back) = slow->next; slow->next = NULL; } } void merge(node **head,node *l1,node *l2) { node *newHead, *curr; if(l1 == NULL) newHead = l2; else if(l2 == NULL) newHead = l1; else { if(l2->key < l1->key) { newHead = l2; l2 = l2->next; } else { newHead = l1; l1 = l1->next; } curr = newHead; while(l1 != NULL && l2 != NULL) { if(l2->key < l1->key) { curr->next = l2; l2 = l2->next; } else { curr->next = l1; l1 = l1->next; } curr = curr->next; } if(l1 == NULL) curr->next = l2; else curr->next = l1; } (*head) = newHead; } void mergeSort(node **head) { node *h1 = NULL; node *h2 = NULL; if((*head) != NULL && (*head)->next != NULL) { split((*head),&h1,&h2); mergeSort(&h1); mergeSort(&h2); merge(head,h1,h2); } }如何正确设置上一个指针？
How to set prev pointers properly ?
我试图在拆分函数中将第二个头的上一个指针设置为NULL prev [back]<-NULL
I tried to set prev pointer of second head to NULL in split function prev[back] <- NULL
我看到了怪胎的递归合并功能，并尝试设置像这样的prev指针
I saw geeks' recursive merge function and tried to set prev pointers like this
prev [next [l2 ]]<-l2 prev [l2]<-NULL;
prev[next[l2]] <- l2 prev[l2] <- NULL;
prev [next [l1]]<-l1 prev [l1]<-NULL;
prev[next[l1]] <- l1 prev[l1] <- NULL;
并且这不能正确设置上一个指针 在这里，我使用了CLRS样式的伪代码
and this don't set prev pointers properly Here i used CLRS style pseudocode
推荐答案我想我是自己做的 由于上一个指针，我不得不逐个节点追加列表的其余部分
I think i did it on my own I had to append rest of the list node by node because of prev pointers
void split(node *head,node **front,node **back) { node *slow, *fast; if(head == NULL || head->next == NULL) { (*front) = head; (*back) = NULL; } else { slow = head; fast = head->next; while(fast != NULL) { fast = fast->next; if(fast != NULL) { slow = slow->next; fast = fast->next; } } (*front) = head; (*back) = slow->next; (*back)->prev = NULL; slow->next = NULL; } } void merge(node **head,node *l1,node *l2) { node *newHead,*curr; if(l1 == NULL) newHead = l2; else if(l2 == NULL) newHead = l1; else { if(l2->key < l1->key) { newHead = l2; l2 = l2->next; } else { newHead = l1; l1 = l1->next; } newHead->prev = NULL; curr = newHead; while(l1 != NULL && l2 != NULL) { if(l2->key < l1->key) { curr->next = l2; l2->prev = curr; l2 = l2->next; } else { curr->next = l1; l1->prev = curr; l1 = l1->next; } curr = curr->next; } while(l1 != NULL) { curr->next = l1; l1->prev = curr; l1 = l1->next; curr = curr->next; } while(l2 != NULL) { curr->next = l2; l2->prev = curr; l2 = l2->next; curr = curr->next; } } (*head) = newHead; } void mergeSort(node **head) { node *h1 = NULL; node *h2 = NULL; if((*head) != NULL && (*head)->next != NULL) { split((*head),&h1,&h2); mergeSort(&h1); mergeSort(&h2); merge(head,h1,h2); } }