leetcode 链表初探 21. merge two sorted lists

原创

阮小七

修改于 2023-01-16 07:07:22

2840

修改于 2023-01-16 07:07:22

文章被收录于专栏：愚公移山愚公移山

以前C++就看链表头疼，干脆做个图示，作为链表题的开始。

题目来了：

https://leetcode.com/problems/merge-two-sorted-lists/

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

要点：

链表是有序的已经

朴素（我的）解法：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if list1 is None:
            return list2
        if list2 is None:
            return list1

        head = ListNode(0)
        cur = head

        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next

        cur.next = list1 or list2

        return head.next

借用例子1：

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

来做个图解，图解的点子来自 https://blog.csdn.net/Varalpha/article/details/104997416，我做个这个题对应更详细的

如果list1 或 list2 是空的，就返回另一个就行了。

从开始 head = {val:0, next:None} 不指向任何ListNode。

然后 cur = head = {val:0, next:None} 开始遍历list1 和list2, 其中一个的遍历完后结束。

第一次：

对比 list1 = {val:1, next : {val:2,next: {val:4, next:None}}} 和 list2 = {val:1, next : {val:3,next: {val:4, next:None}}}

这里接入list2, 就是 cur = head = {val:0, next: list2 = {1, next: {...}}} 把， cur本来指向的None换成了list2的第一个Node

然后 list2 = list2.next = {val:3,next: {val:4, next:None}}, 就是list2现在从原本list2.next开始，

每次不管list1或List2接入cur.next之后， list1或list2更新，然后cur = cur.next = {val:1, next: {...}}, 现在cur从原本cur.next的位置开始。这里其实是指向list2后半部分了，就是next接上了【3，4】, 但是之后的遍历中，next的指向根据val会变

第二次：。。。。。

最后多出来的List1 或list2 整个接到next后面去

然后因为最早第一次的时候cur接到了cur.next也就是head.next后面，那么返回head.next就可以得到之后多次改变指向的cur。

官方给出的递归的方法是：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if list1 is None:
            return list2
        elif list2 is None:
            return list1
        elif list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next,list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list2.next,list1)
            return list2

根据第一个Node哪个list.val小来决定从哪儿开始，简洁，牛的

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

数据结构