Leetcode 21 Merge Two Sorted Lists

发表于 |

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

题意分析：
将两个有序链表合并成一个有序链表，并且题目规定不能单纯新开节点然后赋值，一定要使用给定链表中的节点。

思路分析：
这里给出两种做法，一种迭代，一种递归。

迭代：
用两个指针分别指向两个链表的首部，然后依次比较，将值较小的那个节点加入到结果中。
为了处理两个链表不等长的问题，我默认当链表为空的时候它的值是无穷大！(这样可以使代码更加整洁，因为可以用一个逻辑完成所有的判断)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        # 迭代 28ms,beats 93.46%
        inf = float('inf')
        ret = head = ListNode(0)
        while l1 or l2:
            val1 = l1.val if l1 else inf
            val2 = l2.val if l2 else inf
            if val1 <= val2:
                head.next = l1
                head,l1 = head.next,l1.next
            else:
                head.next = l2
                head,l2 = head.next,l2.next
        return ret.next

递归：
递归的思路用文字描述可能比较麻烦，还是直接看代码吧

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        # 递归 42ms,beats 14.27%
        if not l1: return l2
        if not l2: 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