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

用户头像
Puran
关注
发布于: 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)

  • 迭代,判断两个列表的第一个节点的大小,将较小的值添加到结果中,此时该较小值所在的列表的节点向后移一位,继续来比较。这里需要用到两个指针prevnext ,如果第一个列表的当前节点小于第二个列表,便把第一个列表当前的节点接在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 日 阅读数: 22
用户头像

Puran

关注

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

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

评论

发布
暂无评论
LeetCode | 7. Merge Two Sorted Lists 合并两个有序列表