阅读 214

21_合并两个有序链表

21_合并两个有序链表

目录

  • 21_合并两个有序链表

    • 思路

    • Java 实现

    • Python 实现

    • 思路

    • Java 实现

    • Python 实现

    • 描述

    • 解法一:迭代

    • 解法二:递归

 

描述

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

示例:

输入:1->2->4, 1->3->4输出:1->1->2->3->4->4

解法一:迭代

思路

因为两个链表都是有序链表(递增),因此可以很容易地找出两个链表中的最小元素,即比较两个链表表头的元素,时间复杂度是 O(1)O(1) 的。我们可以利用两个指针——指向两个链表的最小节点,每次比较两个指针所指向节点的值,将值比较小的节点加到新的链表中,然后更新指针,如此循环往复直到到达一个链表的尾部。最后,还需要将另一个链表的剩余部分(如果存在的话)添加到新的链表的尾部。

Java 实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode lastNode = dummyHead;        while (l1 != null && l2 != null) {            if (l1.val < l2.val) {
                lastNode.next = l1;
                l1 = l1.next;
            } else {
                lastNode.next = l2;
                l2 = l2.next;
            }
            
            lastNode = lastNode.next;
        }
        lastNode.next = l1 != null ? l1 : l2;        return dummyHead.next;
    }
}// Runtime: 9 ms// Your runtime beats 86.44 % of java submissions.

复杂度分析:

  • 时间复杂度:O(m+n)O(m+n),其中,mm 为链表 1 的节点数,nn 为链表 2 的节点数,算法需要遍历两个链表的所有元素

  • 空间复杂度:O(1)O(1),只需要保存两个引用

Python 实现

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy_head = last_node = ListNode(0)        while l1 and l2:            if l1.val < l2.val:
                last_node.next = l1
                l1 = l1.next
            else:
                last_node.next = l2
                l2 = l2.next
            
            last_node = last_node.next
        last_node.next = l1 or l2        return dummy_head.next# Runtime: 44 ms# Your runtime beats 99.24 % of python3 submissions.

复杂度分析同上。

解法二:递归

思路

递归的思路和迭代的思路是相同的,都是每次比较两个链表的最小节点,然后对值更小的节点进行操作。不同的是,迭代是从值比较小的节点开始组建新的链表,而递归则是从值比较大的节点开始组建新的链表——递归到其中一个链表的尾部才开始组建新的链表。

Java 实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        if (l1 == null || l2 == null) {            return l1 != null ? l1 : l2;
        }        
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);            return l2;
        }
    }
}// Runtime: 8 ms// Your runtime beats 99.96 % of java submissions.

复杂度分析:

  • 时间复杂度:O(m+n)O(m+n),其中,mm 为链表 1 的节点数,nn 为链表 2 的节点数,算法需要遍历两个链表的所有元素

  • 空间复杂度:O(m+n)O(m+n),额外的空间是由于递归调用占用系统栈的空间,递归的深度最多为 m+nm+n 层

Python 实现

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1 or not l2:            return l1 or l2        
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)            return l1        else:
            l2.next = self.mergeTwoLists(l1, l2.next)            return l2

复杂度分析同上。

来源:https://www.cnblogs.com/shoshana-kong/p/14761413.html

服务器评测 http://www.cncsto.com/ 

服务器测评http://www.cncsto.com/ 


文章分类
后端
文章标签
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐