合并2个有序链表

2019-12-01  本文已影响0人  andy_tu

合并2个有序链表思路:
link1:1->3->5
link2: 2->4->6

首先 判断link1 和 link2 的首节点, 找出数值小的那个节点加到头节点后面变成了一个新链表link3,移动该节点指向他的下一个节点
link3:head->1
link1:3->5
link2:2->4->6
继续取link1 和 link2的头节点比较取出数值较小节点加到link3后面,移动该节点指向他的下一个节点
link3:head->1 ->2
link1:3->5
link2:4->6
........


#include "YXLB.h"
#include <stdlib.h>

typedef struct LinkNode {
    int value;
    struct LinkNode *next;
}linkNode;

linkNode * MegerTwoLink(linkNode *k1, linkNode *k2)
{
    if (k1 == NULL) return k2;
    if (k2 == NULL) return k1;
    
    linkNode *head = alloca(sizeof(linkNode));
    linkNode *curNode = head;
    while (k1 != NULL && k2 != NULL) {
        if (k1->value <= k2->value)
        {
            curNode = curNode->next = k1;
            k1 = k1->next;
        }else{
            curNode = curNode->next = k2;
            k2 = k2->next;
        }
    }
    if (k1 == NULL)
    {
        curNode->next = k2;
    }else if(k2 == NULL){
        curNode->next = k1;
    }
    return head->next;
}


 
linkNode * createLinkNode(int value)
{
    linkNode *node = malloc(sizeof(linkNode));
    node->value = value;
    node->next = NULL;
    return node;
}

void TestMegerTwoLink()
{
    linkNode *n1 = createLinkNode(1);
    linkNode *n2 = createLinkNode(3);
    linkNode *n3 = createLinkNode(5);
    n1->next = n2;
    n2->next = n3;
    printf("链表一:%d->%d->%d \n",n1->value,n2->value,n3->value);
    linkNode *n4 = createLinkNode(2);
    linkNode *n5 = createLinkNode(4);
    linkNode *n6 = createLinkNode(6);
    n4->next = n5;
    n5->next = n6;
    linkNode *K1 =n1;
    linkNode *K2 = n4;
    printf("链表一:%d->%d->%d \n",n4->value,n5->value,n6->value);
    linkNode *head = MegerTwoLink(K1,K2);
    
    printf("新链表:");
    while (head) {
        
        printf(" %d->",head->value);
        
        head = head->next;
    }
}

链表一:1->3->5 
链表一:2->4->6 
新链表: 1-> 2-> 3-> 4-> 5-> 6->
上一篇下一篇

猜你喜欢

热点阅读