两个有序链表序列的合并

题目描述：

给定两个有序链表的头指针 head1 和 head2，请将两个有序链表合并成一个有序链表，并返回合并后的头指针。

示例：

输入：head1 = 1->3->5, head2 = 2->4->6

输出：1->2->3->4->5->6

解题思路：

可以将两个有序链表合并成一个有序链表的过程看作是将两个链表中较小的节点一个一个地取出来进行比较，然后将较小的节点插入到新的链表中。

具体地，可以创建一个虚拟头节点 dummy，然后依次将 head1 和 head2 中较小的节点插入到 dummy 的后面，直到其中一个链表为空。最后，将另一个非空链表的剩余节点直接插入到 dummy 的后面。

最后，返回 dummy 的下一个节点即为合并后的链表的头节点。

代码实现：

Java 代码：

class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

class Solution {
public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (head1 != null && head2 != null) {
if (head1.val <= head2.val) {
cur.next = head1;
head1 = head1.next;
} else {
cur.next = head2;
head2 = head2.next;
}
cur = cur.next;
}
if (head1 != null) {
cur.next = head1;
} else {
cur.next = head2;
}
return dummy.next;
}
}

Python 代码：

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

class Solution:
def mergeTwoLists(self, head1: ListNode, head2: ListNode) -> ListNode:
dummy = ListNode(-1)
cur = dummy
while head1 and head2:
if head1.val <= head2.val:
cur.next = head1
head1 = head1.next
else:
cur.next = head2
head2 = head2.next
cur = cur.next
if head1:
cur.next = head1
else:
cur.next = head2
return dummy.next

时间复杂度分析：

假设 head1 的长度为 m，head2 的长度为 n，则上述算法的时间复杂度为 O(m + n)，因为每个节点只会被遍历一次。

空间复杂度分析：

上述算法的空间复杂度为 O(1)，因为只需要常数个额外的指针变量。