合并两个有序链表
“Think ahead. Don’t let day-to-day operations drive out planning.” — Donald Rumsfeld
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足递增有序的规则。
示例1：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
限制：
0 <= 链表长度 <= 1000
解题思路一：递归法
- 由于链表是升序排列，如果链表1的头结点小于链表2的头结点的值，那么链表1的头结点就是合并后链表的头结点。
- 并将下一层递归函数的返回值，链接到当前结点的尾部。
- 递归终止条件：至少一个为空，返回剩下的那个
class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if l1 == None: return l2 if l2 == None: return l1 if l1.val < l2.val: l1.next = self.mergeTwoLists(l1.next, l2) return l1 else: l2.next = self.mergeTwoLists(l1, l2.next) return l2
解题思路二：双指针比较
分别用指针l1, l2来遍历两个链表，如果当前l1指向的数据小于l2指向的数据，则将l1指向的结点归入合并后的链表，否则将l2指向的结点归并到合并的链表中。
如果有一个链表遍历结束后，则把未结束的链表连接到合并链表后的链表尾部。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if l1 == None: return l2 if l2 == None: return l1 if l1.val >= l2.val: head = l2 l2 = l2.next else: head = l1 l1 = l1.next cur = head while l1 and l2: if l1.val <= l2.val: cur.next = l1 cur = cur.next l1 = l1.next else: cur.next = l2 cur = cur.next l2 = l2.next if l1 == None and l2: cur.next = l2 elif l2 == None and l1: cur.next = l1 return head
解题思路三：虚拟头结点
解题思想跟上述一样，但是为了减少对每一个节点的不同情况进行考虑，可以考虑建立一个虚拟头结点dummy（这是一个很常用的链表题的技巧），然后用一个真正在走的结点cur指向这个dummy，每一个cur都会选取正确的之连接在以dummy为头结点的链表上。
class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: dummy = cur = ListNode(0) while l1 and l2: if l1.val <= l2.val: cur.next = l1 l1 = l1.next else: cur.next = l2 l2 = l2.next cur = cur.next cur.next = l1 if l1 else l2 return dummy.next
时间复杂度: O ( m + n ) O(m+n) O(m+n)，m,n分别为链表l1, l2的长度
空间复杂度: O ( 1 ) O(1) O(1)
感谢你的阅读，这里是不断学习中的yuzhou1su，keep coding, keep loving。
