LeetCode | 21. 合并两个有序链表

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

LeetCode | 21. 合并两个有序链表

OJ链接

  • 定义一个新链表,把小的结点尾插到新的链表
  • 注意在插入新的链表中,1. 空链表,插入的节点就是链表的头节点和尾结点。2. 非空链表,插入的节点就是链表的新的尾结点,头结点不变
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1 == NULL)
        return list2;
    if(list2 == NULL)
        return list1;
    struct ListNode* newTail,*newHead;
    newHead = newTail = NULL;
    struct ListNode* cur1 = list1;
    struct ListNode* cur2 = list2;
    while(cur1 && cur2)
    {
        if(cur1->val<cur2->val)
        {
            //将cur1放入新的链表
            if(newHead == NULL)
            {
                newHead = newTail = cur1;
            }
            else
            {
                newTail->next = cur1;
                newTail = newTail->next;
            }
            cur1 = cur1->next;
        }
        else
        {
            //将cur2放入新的链表
            if(newHead == NULL)
            {
                newHead = newTail = cur2;
            }
            else
            {
                newTail->next = cur2;
                newTail = newTail->next;
            }
            cur2 = cur2->next;
        }
    }
    if(cur1)
    {
        newTail->next = cur1;
    }
    if(cur2)
    {
        newTail->next = cur2;
    }
    return newHead;
}
  • 大家可可以看到这个代码很长,很冗余
  • 需要考虑新链表的头结点为空或者非空,所以导致这里的重复代码比较多
  • 我们还有一个方法,创建一个带头单向不循环链表,后续就不需要考虑节点问题了
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1 == NULL)
        return list2;
    if(list2 == NULL)
        return list1;
    struct ListNode* cur1 = list1;
    struct ListNode* cur2 = list2;
    //创建一个带头单向不循环
    struct ListNode* newTail,*newHead;
    newHead = newTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    while(cur1 && cur2)
    {
        if(cur1->val<cur2->val)
        {
            newTail->next = cur1;
            newTail = newTail->next;
            cur1 = cur1->next;
        }
        else
        {
            newTail->next = cur2;
            newTail = newTail->next;
            cur2 = cur2->next;
        }
    }
    if(cur1)
    {
        newTail->next = cur1;
    }
    if(cur2)
    {
        newTail->next = cur2;
    }
    //把动态开辟的空间释放掉
    struct ListNode* tmp = newHead->next;
    free(newHead);
    return tmp;
}
相关文章
|
3天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
3天前
|
存储 算法 数据可视化
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
|
3天前
|
SQL 算法 数据可视化
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
LeetCode题目92:反转链表ll 【python 递归与迭代方法全解析】
|
3天前
|
存储 传感器 算法
LeetCode题目89:格雷码 递归、迭代及位操作在数组合并中的应用
LeetCode题目89:格雷码 递归、迭代及位操作在数组合并中的应用
|
3天前
|
存储 算法 数据挖掘
LeetCode 题目 88:双指针\直接\递归\插入排序\归并排序 实现合并两个有序数组
LeetCode 题目 88:双指针\直接\递归\插入排序\归并排序 实现合并两个有序数组
|
3天前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
3天前
|
存储 SQL 算法
LeetCode 83题:删除排序链表中的重复元素【面试】
LeetCode 83题:删除排序链表中的重复元素【面试】
|
3天前
|
存储 SQL 算法
LeetCode 题目 82:删除排序链表中的重复元素 II
LeetCode 题目 82:删除排序链表中的重复元素 II
|
3天前
|
算法 数据挖掘 Python
LeetCode题目25 hard:K个一组翻转链表 【分治策略 Python】
LeetCode题目25 hard:K个一组翻转链表 【分治策略 Python】
|
3天前
|
存储 SQL 算法