合并两个有序链表

发表于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

LeetCode题目，21. Merge Two Sorted Lists

先看题目描述

B1j8sS.png

大意就是给定两个有序的链表，让我们将其合并为一个有序链表并返回

算法和思路

迭代

我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。为了方便的返回合并后的链表，我们可以定义一个哨兵节点

算法流程：

  • 定义哨兵节点 prehead，初始化前序节点 pre = prehead
  • 当 l1 和 l2 均不为空时：
    • 比较 l1 和 l2 的节点值的大小，若 l1.val 小于等于 l2.val:
      • 则 pre.next = l1，l1 = l1.next，pre = pre.next
    • 否则：
      • pre.next = l2，l2 = l2.next，pre = pre.next
  • 若 l1 为空：
    • 则 pre.next = l2
  • 否则：
    • pre.next = l1
  • 最终返回 prehead.next

算法源码

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
/**
 * 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; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode preHead = new ListNode(-1);
        ListNode pre = preHead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                pre.next = l1;
                l1 = l1.next;
            } else {
                pre.next = l2;
                l2 = l2.next;
            }
            pre = pre.next;
        }
        if (l1 == null) {
            pre.next = l2;
        } else {
            pre.next = l1;
        }
        return preHead.next;
    }
}