字节二面竟然挂到了这道题上...

作者丨程序员学长

来源丨经授权转自 程序员学长（ID：gh_f585b38c101c）

大家好，我是程序员学长，今天我们来聊一聊链表合并这件事。

前几天群里的小伙伴面试字节，遇到了这么一道题，将二维有序链表变成单链表。今天，我们就来分析一下。

问题描述

给定一个有序链表，其中每个节点也表示一个有序链表。结点包含两个类型的指针：

1. 指向主链表中下一个结点的指针。
2. 指向以此结点为头的链表。

示例如下所示：

  4 ->  9 -> 15 -> 19
  |     |     |     |
  7    13    18    28
  |           |     |
  8          21    37
  |                
  20               
  
 实现函数flatten()，该函数用来将链表扁平化成
 单个链表。例如上面的链表，输出链表为
 
  4 -> 7 -> 8 -> 9 -> 13 -> 15 -> 18 
  ->19 -> 20 -> 21 -> 28 -> 37 

分析问题

拿到这个问题，我们首先需要知道这个问题的考点是什么？题目要求我们把二维有序链表合并成一个单链表，我们来把问题简化一下，假设主链表只有两个节点，即这个二维链表变成如下所示。

  4 ->  9 
  |     |     
  7    13           旋转一下         4 -> 7 -> 8 -> 20
  |               ---------->       |
  8                                 9 -> 13
  |                
  20   

简化之后，我们可以发现这个问题和把二个有序的单链表合并成一个有序的单链表很相似，我们先来看一下如何将二个有序单链表合并成一个有序单链表。

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

class Solution:
    def mergeTwoLists(self, l1, l2):
        if(l1==None):
            return l2
        if(l2==None):
            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

那如果主链表有多个结点呢？我们可以使用归并的思想，逐个去合并就好了，如下图所示。

下面我们来看一下代码如何实现。

class ListNode:
    def __init__(self, val=0, right=None, down=None):
        self.val = val
        self.right = right
        self.down = down

class Solution:
    def mergeTwoLists(self, l1, l2):
        #如果有一个链表为空，则合并后的链表就是另外一个
        if(l1==None):
            return l2
        if(l2==None):
            return l1

        if(l1.val<=l2.val):

            l1.down=self.mergeTwoLists(l1.down,l2)
            return l1
        else:
            l2.down=self.mergeTwoLists(l1,l2.down)
            return l2


    def flatten(self,root):
        if root== None or root.right == None:
            return root
        #把root->right 看作是已经有序的单链表，
        #然后通过递归来进行归并
        return self.mergeTwoLists(root, self.flatten(root.right))
        
     

到目前为止，我们就把这个问题聊完了。

总结

在我们拿到一个问题时，可以先将问题简化，转换成我们熟知的题目，然后再一步步求解，最终把问题解决掉。

最后，我们可以练习一下剑指 Offer II 078. 合并排序链表

我们今天就聊到这里，如果对你有帮助，记得“三连”哦！

你知道的越多，你的思维就越开阔，我们下期见。

点分享

点点赞

点在看