LeetCode | 7. Merge Two Sorted Lists 合并两个有序列表

关注

发布于: 2020 年 07 月 04 日

LeetCode | 7. Merge Two Sorted Lists 合并两个有序列表

Merge Two Sorted Lists 是 LeetCode 算法题库中的第二十一道题，难度为 Easy，题目地址为：https://leetcode.com/problems/merge-two-sorted-lists/
1. 问题描述将两个升序列表合并为一个新的升序列表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
﻿
示例：
输入：1->2->4, 1->3->4
﻿
输出：1->1->2->3->4->4
﻿
2. 解题思路ListNode的定义是：
class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next
本题主要是有两种思路：递归和迭代
递归，将两个列表的第一个节点进行比较，之后再用较小的那个列表剩下的节点组成的列表与较大的列表进行比较，最后输出重新组合成的那个较小的列表。比如，如果list1[0] < list2[0]，list1[0] + merge(list1[1:], list2) 
迭代，判断两个列表的第一个节点的大小，将较小的值添加到结果中，此时该较小值所在的列表的节点向后移一位，继续来比较。这里需要用到两个指针prev 和next ，如果第一个列表的当前节点小于第二个列表，便把第一个列表当前的节点接在prev 节点后面，并将第一个列表的指针向后移一位。
3. 知识点这里最大的知识点是对「递归」概念的理解，即函数在运行时调用自己。
第二个知识点是「指针」。
4. 代码Python 实现递归
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2
        if l2 is 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
﻿
迭代
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        prehead = ListNode(-1)
        
        prev = prehead
        while l1 and l2:
            if l1.val <= l2.val:
                prev.next = l1
                l1 = l1.next
            else:
                prev.next = l2
                l2 = l2.next
            prev = prev.next
            
        prev.next = l1 if l1 is not None else l2
        
        return prehead.next
﻿
﻿
C# 实现递归
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null)
            return l2;
        else if (l2 == null)
            return l1;
        else if (l1.val < l2.val)
        {
            l1.next = MergeTwoLists(l1.next, l2);
            return l1;
        }
        else
        {
            l2.next = MergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}
﻿
迭代
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
        var prehead = new ListNode(-1);
        
        var prev = prehead;
        while (l1 != null && l2 != null)
        {
            if (l1.val <= l2.val)
            {
                prev.next = l1;
                l1 = l1.next;
            } 
            else
            {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
            
        if (l1 != null)
            prev.next = l1;
        else
            prev.next = l2;
        
        return prehead.next;
    }
}
﻿
﻿

发布于: 2020 年 07 月 04 日阅读数: 60

原文链接:【http://xie.infoq.cn/article/5c6066e8b4f212a3617e1d4d8】。文章转载请联系作者。

Puran

关注

GIS从业者，正在往开发的路上小跑。 2018.03.29 加入

从业4年的GIS开发小白，work@esri。

发布

暂无评论

创作场景

LeetCode | 7. Merge Two Sorted Lists 合并两个有序列表

1. 问题描述

2. 解题思路

3. 知识点

4. 代码

Python 实现

C# 实现

Puran

评论