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