问题描述
链接列表伪代码可以在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);
}
}
这篇关于合并排序双链表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!