合并排序双链表 [英] Merge sort doubly linked list

问题描述

链接列表伪代码可以在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);
    }
}

这篇关于合并排序双链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！