合并两个有序链表
问题描述
解题思路
迭代
- 设定一个哨兵节点,prehead,在最后比较容易返回合并后的链表。
- 维护一个prev指针,需要调整prev的next指针
- 重复一下过程:如果l1当前节点的值小于等于l2,就把l1当前节点接在prev节点的后面,同时将l1指针后移一位,否则,对l2做同样的操作。
- 循环终止的时候,l1和l2至多有一个是非空的,由于输入的两个链表都是有序的,所以不管哪个链表是非空的,它包含的所有元素都比前边已经合并的链表中的所有元素都大,意味着 只需要简单地将非空链表接在合并链表后面,并返回合并链表即可。
代码如下
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
prehead = ListNode(-1)
prev = prehead
while l1 and l2:
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next
prev.next = l1 if l1 is not None else l2
return prehead.next