剑指Offer[25]-合并两个排序的链表

题目

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。

示例:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

python代码

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if l1 is None:
            return l2
        if l2 is None:
            return l1

        out_node = ListNode(0)
        _out_node = out_node
        while l1 and l2:
            if l1.val <= l2.val:
                out_node.next = l1
                out_node = l1
                l1 = l1.next
            else:
                out_node.next = l2
                out_node = l2
                l2 = l2.next

        while l1:
            out_node.next = l1
            out_node = l1
            l1 = l1.next

        while l2:
            out_node.next = l2
            out_node = l2
            l2 = l2.next

        return _out_node.next

虽然代码看起来比较多,但是思路很简单也很直观,我们可以将整个解题过程分成两部分。

第一步:

        out_node = ListNode(0)
        _out_node = out_node

        while l1 and l2:
            if l1.val <= l2.val:
                out_node.next = l1
                out_node = l1
                l1 = l1.next
            else:
                out_node.next = l2
                out_node = l2
                l2 = l2.next

首先我们会声明一个新的节点,因为最后我们要返回新链表,所以我们要将链表的头部保存一个副本。紧接着while部分就是第一步处理,大致过程可以概括为:首先判断l1和l2各自节点的值的大小,因为我们需要构造一个递增链表,所以只需要依次找到值小的那个节点接在out_node后面即可。

举个例子:

  • 比如当前l1链表为1-4-5,l2链表为2-3-9,out_node链表初始化为0。
  • 首先比较l1和l2的第一个节点,因为1<2,所以将1接在out_node后面,out_node变为0-1,因为这次是l1的节点被处理了,所以还要更新l1的指针,指向下一个待处理节点(out_node同理)。
  • 继续比较l1和l2节点,此时4>2,小值出现在l2,处理方法同上,out_node变为0-1-2,并更新l2和out_node的指针。

因为l1和l2长度不一定相等,所以这一步处理后,长的链表还会剩余一部分没有遍历,但是可以肯定的是这一部分是有序的,直接接在out_node后面即可。

第二步:

        while l1:
            out_node.next = l1
            out_node = l1
            l1 = l1.next

        while l2:
            out_node.next = l2
            out_node = l2
            l2 = l2.next

将未处理的部分直接加在out_node后面。

注意最后函数返回的是_out_node.next,_out_node的作用就是保存链表头部。

发表评论

电子邮件地址不会被公开。