leetcode:21. 合并两个有序链表

简介: leetcode:21. 合并两个有序链表

一、题目

 

函数原型:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)

二、思路

合并两个有序链表为一个新的升序链表,只需要遍历两个有序链表并比较结点值大小,依次将较小的结点尾插到新链表即可。

三、代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode *newhead=NULL;//新链表
    struct ListNode *tail=NULL;//新链表尾指针
    struct ListNode *cur1=list1;//遍历指针1
    struct ListNode *cur2=list2;//遍历指针2
    while(cur1&&cur2)
    {
        if(cur1->val<=cur2->val)//选取较小结点尾插
        {
            if(tail==NULL)//尾指针为空,先要将插入的结点作为头结点
            {
                newhead=tail=cur1;
            }
            else
            {
                tail->next=cur1;
                tail=cur1;
            }
            cur1=cur1->next;
        }
        else
        {
            if(tail==NULL)
            {
                newhead=tail=cur2;//尾指针为空,先要将插入的结点作为头结点
            }
            else
            {
                tail->next=cur2;
                tail=cur2;
            }
            cur2=cur2->next;
        }
    }
    if(cur1)//链表1还有剩余结点,尾插到新链表
    {
        if(tail==NULL)
        {
            newhead=tail=cur1;
        }
        else
        {
            tail->next=cur1;
        }
    }
    if(cur2)//链表2还有剩余结点,尾插到新链表中
    {
        if(tail==NULL)
        {
            newhead=tail=cur2;
        }
        else
        {
            tail->next=cur2;
        }
    }
    return newhead;
}




目录
相关文章
|
4天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
12小时前
|
Java Python
二刷力扣--链表
二刷力扣--链表
|
1天前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
4天前
|
存储 算法 数据可视化
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
|
5天前
|
SQL 算法 数据可视化
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
|
5天前
|
存储 传感器 算法
LeetCode题目89:格雷码 递归、迭代及位操作在数组合并中的应用
LeetCode题目89:格雷码 递归、迭代及位操作在数组合并中的应用
|
5天前
|
存储 算法 数据挖掘
LeetCode 题目 88:双指针\直接\递归\插入排序\归并排序 实现合并两个有序数组
LeetCode 题目 88:双指针\直接\递归\插入排序\归并排序 实现合并两个有序数组
|
5天前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
5天前
|
存储 SQL 算法
LeetCode 83题:删除排序链表中的重复元素【面试】
LeetCode 83题:删除排序链表中的重复元素【面试】
|
5天前
|
存储 SQL 算法
LeetCode 题目 82:删除排序链表中的重复元素 II
LeetCode 题目 82:删除排序链表中的重复元素 II