力扣00021.合并两个有序链表

发表于 分类于 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 7 分钟
合并两个有序链表、递归、链表、简单

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* current = dummy;
        while (list1 && list2) {
            if (list1->val <= list2->val) {
                current->next = list1;
                list1 = list1->next;
            } else {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
        }
        current->next = list1 ? list1 : list2;
        return dummy->next;
    }
};

结果

执行用时 : 8 ms, 击败 55.64% 使用 C++ 的用户

内存消耗 : 14.73 MB, 击败 77.93% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        current.next = (list1 != null) ? list1 : list2;
        return dummy.next;
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Java 的用户

内存消耗 : 41.36 MB, 击败 9.94% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 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):
        dummy = ListNode(-1)
        current = dummy
        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next
        current.next = list1 if list1 else list2
        return dummy.next

结果

执行用时 : 16 ms, 击败 94.38% 使用 Python 的用户

内存消耗 : 12.98 MB, 击败 77.98% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

结果

执行用时 : 48 ms, 击败 47.07% 使用 Python3 的用户

内存消耗 : 16.86 MB, 击败 15.63% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode dummy;
    struct ListNode* current = &dummy;
    dummy.next = NULL;
    while (list1 && list2) {
        if (list1->val <= list2->val) {
            current->next = list1;
            list1 = list1->next;
        } else {
            current->next = list2;
            list2 = list2->next;
        }
        current = current->next;
    }
    current->next = (list1 != NULL) ? list1 : list2;
    return dummy.next;
}

结果

执行用时 : 4 ms, 击败 70.71% 使用 C 的用户

内存消耗 : 6.79 MB, 击败 33.43% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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 list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        current.next = (list1 != null) ? list1 : list2;
        return dummy.next;
    }
}

结果

执行用时 : 68 ms, 击败 87.27% 使用 C# 的用户

内存消耗 : 40.66 MB, 击败 15.22% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    let dummy = new ListNode(-1);
    let current = dummy;
    while (list1 !== null && list2 !== null) {
        if (list1.val <= list2.val) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }
    current.next = list1 !== null ? list1 : list2;
    return dummy.next;
};

结果

执行用时 : 80 ms, 击败 16.68% 使用 JavaScript 的用户

内存消耗 : 49.72 MB, 击败 13.06% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    if (list1 === null) {
        return list2;
    }
    if (list2 === null) {
        return list1;
    }
    if (list1.val <= list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

结果

执行用时 : 80 ms, 击败 28.31% 使用 TypeScript 的用户

内存消耗 : 50.95 MB, 击败 8.20% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

    /**
     * @param ListNode $list1
     * @param ListNode $list2
     * @return ListNode
     */
    function mergeTwoLists($list1, $list2) {
        $dummy = new ListNode(-1);
        $current = $dummy;
        while ($list1 !== null && $list2 !== null) {
            if ($list1->val <= $list2->val) {
                $current->next = $list1;
                $list1 = $list1->next;
            } else {
                $current->next = $list2;
                $list2 = $list2->next;
            }
            $current = $current->next;
        }
        $current->next = ($list1 !== null) ? $list1 : $list2;
        return $dummy->next;
    }
}

结果

执行用时 : 8 ms, 击败 73.13% 使用 PHP 的用户

内存消耗 : 19.55 MB, 击败 5.97% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        guard let l1 = list1 else { return list2 }
        guard let l2 = list2 else { return list1 }
        if l1.val < l2.val {
            l1.next = mergeTwoLists(l1.next, l2)
            return l1
        } else {
            l2.next = mergeTwoLists(l1, l2.next)
            return l2
        }
    }
}

结果

执行用时 : 16 ms, 击败 14.80% 使用 Swift 的用户

内存消耗 : 15.41 MB, 击败 5.06% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
        if (list1 == null) {
            return list2
        }
        if (list2 == null) {
            return list1
        }
        if (list1.`val` <= list2.`val`) {
            list1.next = mergeTwoLists(list1.next, list2)
            return list1
        } else {
            list2.next = mergeTwoLists(list1, list2.next)
            return list2
        }
    }
}

结果

执行用时 : 200 ms, 击败 6.76% 使用 Kotlin 的用户

内存消耗 : 34.70 MB, 击败 52.03% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * class ListNode {
 *   int val;
 *   ListNode? next;
 *   ListNode([this.val = 0, this.next]);
 * }
 */
class Solution {
  ListNode? mergeTwoLists(ListNode? l1, ListNode? l2) {
    ListNode dummy = ListNode(0);
    ListNode? current = dummy;
    while (l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        current!.next = l1;
        l1 = l1.next;
      } else {
        current!.next = l2;
        l2 = l2.next;
      }
      current = current.next;
    }
    current!.next = l1 ?? l2;
    return dummy.next;
  }
}

结果

执行用时 : 372 ms, 击败 6.67% 使用 Dart 的用户

内存消耗 : 147.40 MB, 击败 93.33% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	dummy := &ListNode{}
	current := dummy
	for list1 != nil && list2 != nil {
		if list1.Val <= list2.Val {
			current.Next = list1
			list1 = list1.Next
		} else {
			current.Next = list2
			list2 = list2.Next
		}
		current = current.Next
	}
	if list1 != nil {
		current.Next = list1
	} else {
		current.Next = list2
	}
	return dummy.Next
}

结果

执行用时 : 4 ms, 击败 36.50% 使用 Go 的用户

内存消耗 : 2.35 MB, 击败 60.06% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} list1
# @param {ListNode} list2
# @return {ListNode}
def merge_two_lists(list1, list2)
  dummy = ListNode.new(-1)
  current = dummy
  while list1 && list2
    if list1.val <= list2.val
      current.next = list1
      list1 = list1.next
    else
      current.next = list2
      list2 = list2.next
    end
    current = current.next
  end
  current.next = list1 || list2
  dummy.next
end

结果

执行用时 : 56 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 206.81 MB, 击败 22.22% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * class ListNode(_x: Int = 0, _next: ListNode = null) {
 *   var next: ListNode = _next
 *   var x: Int = _x
 * }
 */
object Solution {
  def mergeTwoLists(list1: ListNode, list2: ListNode): ListNode = {
    if (list1 == null) {
      return list2
    }
    if (list2 == null) {
      return list1
    }
    if (list1.x <= list2.x) {
      list1.next = mergeTwoLists(list1.next, list2)
      return list1
    } else {
      list2.next = mergeTwoLists(list1, list2.next)
      return list2
    }
  }
}

结果

执行用时 : 488 ms, 击败 100.00% 使用 Scala 的用户

内存消耗 : 56.16 MB, 击败 94.12% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn merge_two_lists(mut list1: Option<Box<ListNode>>, mut list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut dummy = Some(Box::new(ListNode { val: 0, next: None }));
        let mut current = &mut dummy;
        while let (Some(node1), Some(node2)) = (list1.as_deref_mut(), list2.as_deref_mut()) {
            if node1.val <= node2.val {
                current.as_mut().unwrap().next = list1.take();
                list1 = current.as_mut().unwrap().next.as_deref_mut().unwrap().next.take();
            } else {
                current.as_mut().unwrap().next = list2.take();
                list2 = current.as_mut().unwrap().next.as_deref_mut().unwrap().next.take();
            }
            current = &mut current.as_mut().unwrap().next;
        }
        current.as_mut().unwrap().next = list1.or(list2);
        dummy.unwrap().next
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.04 MB, 击败 56.83% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
%% Definition for singly-linked list.
%%
%% -record(list_node, {val = 0 :: integer(),
%%                     next = null :: 'null' | #list_node{}}).

merge_two_lists(List1, List2) ->
    case {List1, List2} of
        {null, List2} -> List2;
        {List1, null} -> List1;
        {Node1 = #list_node{val = Val1, next = Next1}, Node2 = #list_node{val = Val2, next = Next2}} ->
            if Val1 =< Val2 ->
                Node1#list_node{next = merge_two_lists(Next1, Node2)};
            true ->
                Node2#list_node{next = merge_two_lists(Node1, Next2)}
            end
    end.

结果

执行用时 : 268 ms, 击败 -% 使用 Erlang 的用户

内存消耗 : 59.08 MB, 击败 -% 使用 Erlang 的用户

Elixir

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for singly-linked list.
#
# defmodule ListNode do
#   @type t :: %__MODULE__{
#           val: integer,
#           next: ListNode.t() | nil
#         }
#   defstruct val: 0, next: nil
# end

defmodule Solution do
  @spec merge_two_lists(list1 :: ListNode.t | nil, list2 :: ListNode.t | nil) :: ListNode.t | nil
  def merge_two_lists(nil, list2), do: list2
  def merge_two_lists(list1, nil), do: list1
  def merge_two_lists(%ListNode{val: val1, next: next1} = list1, %ListNode{val: val2, next: next2} = list2) do
    if val1 <= val2 do
      %ListNode{val: val1, next: merge_two_lists(next1, list2)}
    else
      %ListNode{val: val2, next: merge_two_lists(list1, next2)}
    end
  end
end

结果

执行用时 : 344 ms, 击败 -% 使用 Elixir 的用户

内存消耗 : 67.86 MB, 击败 -% 使用 Elixir 的用户