剑指Offer之面试题25: 合并两个排序的链表

3 years ago

source link: https://blog.51cto.com/yuzhou1su/5141827
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

合并两个有序链表

“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) $$，m,n 分别为链表 l1, l2 的长度
空间复杂度: $$ O(1) $$