当前位置：
  1. 首页
  2. 数据结构与算法
  3. 算法系统课
  4. 正文

LeetCode21. 合并两个有序链表🌟🌟🌟简单

算法系统课 免费

问题描述

原文链接：21. 合并两个有序链表

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

示例 1：

img

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

代码实现

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 视频里忘了说，其实这个判断可以优化掉，下面的逻辑已经包含了
        // if(list1 == null){
        //     return list2;
        // }
        // if(list2 == null){
        //     return list1;
        // }
        ListNode list3 = new ListNode(-1);
        ListNode temp = list3;

        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
               temp.next = list1;
               list1 = list1.next;

            } else {
               temp.next = list2;
               list2 = list2.next;
            }
            temp = temp.next;
        }

        // if(list1 != null){
        //     temp.next = list1;
        // }
        // if(list2 != null){
        //     temp.next = list2;
        // }
        // 上面两个也能优化一下，我视频里也忘了说
        temp.next = list1 == null ? list2 : list1;  
        return list3.next;
    }
}

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        # 视频里忘了说，其实这个判断可以优化掉，下面的逻辑已经包含了
        # if(list1 == null){
        #     return list2;
        # }
        # if(list2 == null){
        #     return list1;
        # }
        list3 = ListNode(-1)
        temp = list3

        while list1 != None and list2 != None:
            if list1.val <= list2.val:
               temp.next = list1
               list1 = list1.next
            else:
               temp.next = list2
               list2 = list2.next
            temp = temp.next

        # if list1 != None:
        #     temp.next = list1
        # if list2 != None:
        #     temp.next = list2
        # 上面两个也能优化一下，我视频里也忘了说
        temp.next = list1 if list1 != None else list2
        return list3.next

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 视频里忘了说，其实这个判断可以优化掉，下面的逻辑已经包含了
        // if(list1 == null){
        //     return list2;
        // }
        // if(list2 == null){
        //     return list1;
        // }
        ListNode* list3 = new ListNode(-1);
        ListNode* temp = list3;

        while(list1 != nullptr && list2 != nullptr){
            if(list1->val <= list2->val){
               temp->next = list1;
               list1 = list1->next;
            } else {
               temp->next = list2;
               list2 = list2->next;
            }
            temp = temp->next;
        }

        // if(list1 != nullptr){
        //     temp->next = list1;
        // }
        // if(list2 != nullptr){
        //     temp->next = list2;
        // }
        // 上面两个也能优化一下，我视频里也忘了说
        temp->next = list1 == nullptr ? list2 : list1;  
        return list3->next;
    }
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    // 视频里忘了说，其实这个判断可以优化掉，下面的逻辑已经包含了
    // if(list1 == nil){
    //     return list2;
    // }
    // if(list2 == nil){
    //     return list1;
    // }
    list3 := &ListNode{Val: -1}
    temp := list3

    for list1 != nil && list2 != nil {
        if list1.Val <= list2.Val {
            temp.Next = list1
            list1 = list1.Next
        } else {
            temp.Next = list2
            list2 = list2.Next
        }
        temp = temp.Next
    }

    // if list1 != nil {
    //     temp.Next = list1
    // }
    // if list2 != nil {
    //     temp.Next = list2
    // }
    // 上面两个也能优化一下，我视频里也忘了说
    if list1 == nil {
        temp.Next = list2
    } else {
        temp.Next = list1
    }
    return list3.Next
}

发表回复

后才能评论

评论(7)

  • 少年不识流川枫 永久会员 2024年2月28日 上午1:43 
    class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // if(list1 == null){
        //     return list2;
        // }
        // if(list2 == null){
        //     return list1;
        // }
        // 最后循环完肯定有其中一个剩下一个，此时刚好与上面两个if重了，此时需要将那个节点也加到temp.next
        ListNode list3 = new ListNode(-1);
        ListNode temp = list3;
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                temp.next = list1;
                list1 = list1.next;
            }else{
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }
        temp.next = list1 == null? list2 : list1;
        return list3.next;
    }
}
  • Yuki 永久会员 2024年1月30日 下午4:39

    打卡
    class Solution {
    public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNodedummyhead=new ListNode(0);
    ListNode    cur=dummyhead;

        while(list1!=nullptr&&list2!=nullptr){
        //找到指向值更小节点的指针
        ListNode*p=(list1->val<list2->val)?list1:list2;
        cur->next=p;
        cur=cur->next;
        p=p->next;//移动小值节点的指针
    }

    cur->next=(list1==nullptr)?list2:list1;

    return dummyhead->next;
}

    };
    /*
    设置头结点
    找到更小节点并连接
    移动小值节点的指针
    妥善处理最后一个节点
    */

  • uu 永久会员 2023年9月21日 下午2:44 
    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(-1);
        ListNode ans = head;

        while(list1 != null) {
            if(list2 == null) {
                head.next = list1;
                break;
            }
            head.next = list1.val < list2.val ? list1 : list2;
            if(head.next == list1) {
                list1 = list1.next;
            } else if(head.next == list2) {
                list2 = list2.next;
            }
            head = head.next;
        }
        if(list2 != null) {
            head.next = list2;
        }
        return ans.next;
    }
}
  • 泡芙 永久会员 2023年9月8日 下午5:38

    双指针

    • Time：O(n+m)，n和m分别为链表l1, l2的长度,合并操作需遍历两链表。
    • Space：O(1)
    class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode temp = dummyHead;

        while (list1 != null && list2 != null) {
            // 比较list1和list2两个指针
            // 将值较小的节点接到temp指针
            if (list1.val < list2.val) {
                temp.next = list1;
                list1 = list1.next;
            } else {
                temp.next = list2;
                list2 = list2.next;
            }
            // temp指针不断向前
            temp = temp.next;
        }

        temp.next = list1 == null ? list2 : list1;

        return dummyHead.next;
    }
}
  • AD钙奶 普通 2023年9月1日 下午3:15

    打卡

    class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode res = new ListNode(0);
        ListNode cur = res;

        while(list1 != null && list2 != null) {
            if(list1.val <= list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 == null ? list2 : list1;
        return res.next;
    }
}
  • 阿尚 普通 2023年8月18日 下午2:05 
    class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        ListNode p1 = list1;
        ListNode p2 = list2;

        //虚拟节点
        ListNode dummyNode = new ListNode(-1);
        ListNode pre = dummyNode;

        while(p1 != null && p2 != null){
            if(p1.val < p2.val){
                pre.next = p1;
                p1 = p1.next;
            }else{
                pre.next = p2;
                p2 = p2.next;
            }
            pre = pre.next;
        }

        if(p1 == null){
            pre.next = p2;
        }else{
            pre.next = p1;
        }

        return dummyNode.next;
    }
}
  • 帅气的冬瓜 普通 2023年6月28日 下午6:01

    打卡

如果您已经成功付款但是网站没有弹出成功提示，请联系站长提供付款信息为您处理