合并两个有序链表

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

示例:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
思路
有两种方法,一个不用递归,另一个用递归

解题

一、不用递归的解法

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if l1 is None and l2 is None:
            return None
        new_list = ListNode(0)
        pre = new_list
        while l1 is not None and l2 is not None:
            if l1.val < l2.val:
                pre.next = l1
                l1 = l1.next
            else:
                pre.next = l2
                l2 = l2.next
            pre = pre.next
        if l1 is not None:
            pre.next = l1
        else:
            pre.next = l2
        return new_list.next

首先,因为之前不是很懂 python 里链表这种表示方法,经过一些代码实操,现在明白了,在第一个 ListNode 这种类表示方法里,如果只有 __init__ 这个定义函数,那这个类的实例化对象只能表示一个节点,它虽然具有初始节点值,也有.next 这个定义,但没有接下来其他类函数去定义节点关系,那它就只能表示一个节点。仔细看下面

head1 = ListNode(2)
n1 = ListNode(3)
n2 = ListNode(4)
n3 = ListNode(9)
head1.next = n1
n1.next = n2
n2.next = n3

head2 = ListNode(3)
m1 = ListNode(5)
m2 = ListNode(7)
m3 = ListNode(8)
head2.next = m1
m1.next = m2
m2.next = m3
while head1:
    print(head1.val)
    head1 = head1.next
while head2:
    print(head2.val)
    head2 = head2.next

#2
4
3
7

第一段代码其实定义了两个有序链表,分别是 2–>3–>4–>9 和 3–>5–>7–>8,因为 ListNode 类的实例化对象只是节点,所以上面所做的就是把分别定义四个节点,然后通过 python 里面的这种 "=" 赋值方法把节点依次传递下去,比如 head1 的下一个节点是 n1,这样就把两个链表造好了(当然在完整的单链表构造中,有 append、insert、pop、appendleft 等方法)

我们再回到解法里面,l1 和 l2 其实是两个链表的头节点,当他们都不存在的时候,那就直接返回 None 了,没毛病;然后,

new_list = ListNode(0) 这个意思是构造一个初始节点,也就是新链表的初始节点,其实可以把 new_list 理解为根节点;接着下一步是 pre = new_list,这一步很关键,因为如果不赋值的话,让 new_list 自身去不断 next 传递节点关系,
那根节点就找不到了,所以需要先把 new_list 保存,接着进行一个 while 循环,条件是 l1 和 l2 这两个节点都不能为空,也就是说在两个链表长度范围之内遍历,当 l1(初始是链表 1 的头节点)的值小于 l2 的值,那就把 pre 的指向 l1,其实也就是 new_list
指向了 l1,下面的步骤应该不难理解了;最后循环结束了,肯定是其中有一个链表被遍历完了,也就是 l1 或者 l2 传递到了这两个链表的尾节点,没法再 next 下去了。
跳出循环,此时来到了接下来的 if l1 is not None: 这个判断条件,我们假设遍历完以后,l1 所在的链表 1 还有剩余的几个节点,l2 所在的链表 2 已经遍历完了,那么 pre.next = l1 这个意思就是把 pre 引向 l1 之后的那几个节点,也就是把新链表跟剩下
的链表连接起来
最后 return 的是 new_list.next,因为 new_list 是根节点,new_list.next 才是头节点!

二、用递归的解法

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1:
            return l2
        if not l2:
            return l1
        if l1.val <= l2.val:
            ret = l1
            ret.next = self.mergeTwoLists(l1.next, l2)
        else:
            ret = l2
            ret.next = self.mergeTwoLists(l1, l2.next)
        return ret