老青菜

剑指offer-单链表合并

2017-01-24

题目

有两个已经排序的链表,合并这两个链表,输出新的链表。

分析

合并两个链表,我们可以依次对比两个链表的节点:

  1. 对比头节点a、b,决定使用哪一个头节点
  2. 如果a<b,那么a放在前面,a指向后一个节点,即 a=a.next,准备比较 a 和b。
  3. 如果a=>b,b作为头节点,b指向后一个节点,即 b=b.next,准备比较 a 和b。
  4. 重复上面的步骤,直到有一个链表已经遍历完成。
  5. 最后把多余的链表节点追加到当前链表后面。

实现

//合并单链表
ZHNode *mergeLinkList(ZHNode *node1, ZHNode *node2) {
    //如果有一个链表为空,返回另外一个链表
    if (node1 == NULL || node2 == NULL) {
        return node2?node2:node1;
    }
    ZHNode *hNode = NULL;
    ZHNode *lastNode = NULL;
    //两个链表节点两两比较
    while (node1 != NULL && node2 != NULL) {
        ZHNode *tmpNode = NULL;
        if (node1->data<node2->data) {
            //node1 小于 node2,比对结果使用 node1
            tmpNode = node1;
            //下次拿 node1.next和node2比较,更新node1
            node1 = node1->next;

        } else if (node1->data>=node2->data) {
            //node1 大于 node2,比对结果使用 node2
            tmpNode = node2;
            //下次拿 node1和node2.next比较,更新node2
            node2 = node2->next;
        }
        if (lastNode == NULL) {
            //找到正确的头节点
            lastNode = tmpNode;
            hNode = tmpNode;
        } else {
            //其他节点
            lastNode->next = tmpNode;
            lastNode = lastNode->next;
        }
    }
    //node1链表可能还有多余的节点
    if (node1 != NULL) {
        lastNode->next = node1;
    } else if (node2 != NULL) {
        lastNode->next = node2;
    }
    return hNode;
}

添加测试代码:

//创建链表 node1
ZHNode *hNode1 = malloc(sizeof(ZHNode));
hNode1->data = 1;
ZHNode *lastNode1 = hNode1;
for (int i=3; i<=15; i+=2) {
    ZHNode *nextNode = malloc(sizeof(ZHNode));
    nextNode->data = i;
    lastNode1->next = nextNode;
    lastNode1 = nextNode;
}
//创建链表 node2
ZHNode *hNode2 = malloc(sizeof(ZHNode));
hNode2->data = 2;
ZHNode *lastNode2 = hNode2;
for (int i=4; i<=12; i+=2) {
    ZHNode *nextNode = malloc(sizeof(ZHNode));
    nextNode->data = i;
    lastNode2->next = nextNode;
    lastNode2 = nextNode;
}
//合并
ZHNode *tmpNode = mergeLinkList(hNode1, hNode2);
//输出结果
while (tmpNode) {
    printf("%d,", tmpNode->data);
    tmpNode = tmpNode->next;
}

最后输出结果:

1,2,3,4,5,6,7,8,9,10,11,12,13,15,
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章