LeetCode-合并有序链表

发表于 | 分类于 | 阅读次数:

题目

出处：LeetCode 算法第21题

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

示例：

1
2
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

思路

遍历解法

  • 先判断链表为空的情况
  • 创建一个新链表，并在其前面加上一个哑节点，用于简化各种极端操作
  • 创建一个指针，指向这个哑节点
  • 循环判断 两个链表头节点值的大小 ，谁的值小将谁传入新链表
  • 如果两个链表不一样长，剩余的部分也要加在新链表的后面

递归算法

  • 递归算法写出来看着十分简洁，就是如果太多层的调用的话，调用太多栈会性能下降
  • 谁的头节点小，就将该头节点作为最终链表的头节点
  • 再一层层递归下去，反复调用自身函数，成功将链表合并
  • 需要注意的是：如果两链表长度不想等，一定要在后面加上长链表剩余的部分

代码

遍历

1
2
3
4
5
6
7
public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        }
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        curr.next = (l1 == null) ? l2 : l1;
        return dummy.next;
    }

递归

1
2
3
4
5
6
7
8
9
10
11
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }