21. 合并两个有序链表【LeetCode 刷题日记】

记录自己从零开始刷 LeetCode，提高自己的数据结构与算法能力，为了获得更好的工作机会

链表 简单

题目：21. 合并两个有序链表
地址：https://leetcode.cn/problems/merge-two-sorted-lists/solutions/226408/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/?envType=study-plan-v2&envId=selected-coding-interview

解题情况

• 没有解出来，不知道如何下笔

参考优秀题解

方法一：递归

• 时间复杂度：O(m + n)，m 和 n 分别是两个链表的长度，最多递归调用每个节点
• 空间复杂度：O(m + n)，m 和 n 分别是两个链表的长度，递归需要消耗栈空间，栈空间大小取决于递归调用深度

/**
 - Definition for singly-linked list.
 - function ListNode(val, next) {
 - this.val = (val===undefined ? 0 : val)
 - this.next = (next===undefined ? null : next)
 - }
 */

/**
 - @param {ListNode} l1
 - @param {ListNode} l2
 - @return {ListNode}
 */

var mergeTwoLists = function (l1, l2) {
  if (!l1) return l2;
  if (!l2) return l1;

  if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
};

方法二：迭代

• 时间复杂度：O(m + n)，m 和 n 分别是两个链表的长度，最多不出过两个链表长度之和
• 空间复杂度：O(1)，变量空间为常数级

/**
 - Definition for singly-linked list.
 - function ListNode(val, next) {
 - this.val = (val===undefined ? 0 : val)
 - this.next = (next===undefined ? null : next)
 - }
 */

/**
 - @param {ListNode} l1
 - @param {ListNode} l2
 - @return {ListNode}
 */

var mergeTwoLists = function (l1, l2) {
  const prehead = new ListNode(-1);

  let 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;
  }

  prev.next = l1 === null ? l2 : l1;

  return prehead.next;
};

复盘

问题点：

• 我看到好像是数组，然后一直用 forEach 和 for 循环遍历，但是其实题目中已经给出了入参类型为 ListNode，自己没有理解清楚
• 对链表结构不熟悉
• 对递归操作不熟悉

提升点：

• 熟悉链表结构
• 熟悉递归操作