21. 合并两个有序链表

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

  1. 示例 1:

    demo

    1
    2
    输入:l1 = [1,2,4], l2 = [1,3,4]
    输出:[1,1,2,3,4,4]
  2. 示例 2:

    1
    2
    输入:l1 = [], l2 = []
    输出:[]
  3. 示例 3:

    1
    2
    输入:l1 = [], l2 = [0]
    输出:[0]
  • 提示:

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

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 思路:递归
var mergeTwoLists = function(l1, 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;
}
};

206. 反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

  1. 示例 1:

    demo1

    1
    2
    输入:head = [1,2,3,4,5]
    输出:[5,4,3,2,1]
  2. 示例 2:

    demo2

    1
    2
    输入:head = [1,2]
    输出:[2,1]
  3. 示例 3:

    1
    2
    输入:head = []
    输出:[]
  • 提示:

    1
    2
    链表中节点的数目范围是 [0, 5000]
    -5000 <= Node.val <= 5000

题 解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 思路:迭代
// 在遍历链表时,将当前节点的 next 指针改为指向前一个节点。
// 由于节点没有引用其前一个节点,因此必须事先存储其前一个节点。
// 在更改引用之前,还需要存储后一个节点。最后返回新的头引用。

var reverseList = function(head) {
let prev = null;
let curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
};