[数据结构与算法]力扣21. 合并两个有序链表

2021.08.15
记录自己的力扣刷题之旅

前言

一、题目：合并两个有序链表

原题链接------->点击查看原题链接

题干：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

二、C语言解决方案

1.题目分析

1. 本题我的实现方法使用了头结点去指向新的链表的头部，（当然没有头指针也能实现）所以最后return l3->next;
2. 需要同时遍历两个链表序列并找出谁的数值最小，然后让 l3 指向这个数小一点的结点，

 while(l1&&l2){
        if(l1->val<=l2->val){
            P->next=l1;
            P=P->next;
            l1=l1->next;
        }
        else{
            P->next=l2;
            P=P->next;
            l2=l2->next;
        }
    }

3. 然后在遍历链表剩下的，因为不知道谁先空，所以两个都需要：

    while(l1){
        P->next=l1;
        l1=l1->next;
        P=P->next;
    }
    while(l2){
        P->next=l2;
        l2=l2->next;
        P=P->next;
    }

4. 最后不要忘记了，将最后一个结点的下一位的位置指针指向NULL；P->next=NULL;

2.C语言代码实现

完整代码如下：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* l3=(struct ListNode*)malloc(sizeof(struct ListNode));
    l3->next=NULL;
    struct ListNode* P=l3;
    while(l1&&l2){
        if(l1->val<=l2->val){
            P->next=l1;
            P=P->next;
            l1=l1->next;
        }
        else{
            P->next=l2;
            P=P->next;
            l2=l2->next;
        }
    }
    while(l1){
        P->next=l1;
        l1=l1->next;
        P=P->next;
    }
    while(l2){
        P->next=l2;
        l2=l2->next;
        P=P->next;
    }
    P->next=NULL;


    return l3->next;
}

三、代码实现截图展示

总结

1. 首先同时遍历两个链表去对比大小，然后记得将剩余的也放入 l3 ；
2. 最后不要忘记将最后一个结点的下一个位置指向NULL；（当然此步骤有点多此一举，也不是默认是指向NULL，而是说原先 l1 或 l2 在创建的时候就已经将最后一个指向了NULL，那么我们将最后一个结点给予给了 l3 那么最后一个结点当然还是指向NULL，所以分析回来，此步骤多此一举，但是保险起见，还是书写为好！）
3. 坚持坚持坚持。