反转链表、删除链表的倒数第N个节点、合并两个有序链表和两数相加

反转链表
反转一个单链表。
示例
1
输入: 1->2->3->4->5->NULL
2
输出: 5->4->3->2->1->NULL
Copied!
方法一
思路
用迭代的方法实现。
详解
1.先判断链表是否为空或者只有一个元素，是的话直接返回；
2.若链表不仅有一个元素，先开辟一个空间存头指针，再把旧的头指针变为新的尾指针；
3.遍历链表，申请一个新的临时空间用于前后元素交换即可。
1
const reverseList = function (head) {
2
  if (head === null || head.next === null) {
3
    return head;
4
  }
5
  let p = head.next;
6
  head.next = null; // 旧的头指针是新的尾指针,next需要指向null
7
  while (p !== null) {
8
    const temp = p.next; // 先保留下一个step要处理的指针
9
    p.next = head; // 然后p和head进行反向
10
    head = p; // 指针后移
11
    p = temp; // 指针后移
12
  }
13
  return head;
14
};
Copied!
复杂度分析
时间复杂度： O(n)O(n)O(n)
​
上述解法中，遍历了一次链表，这将耗费 O(n)O(n)O(n)
 的时间。
空间复杂度： O(1)O(1)O(1)
​
上述解法中，申请了两个额外的临时存储空间，这将耗费 O(1)O(1)O(1)
 的空间。
方法二
思路
用递归的方法实现。
详解
1.先判断链表是否为空或只有一个元素，是的话直接返回；
2.若链表不仅有一个元素，则递归的调用链表反转方法。
递归演示：
1
const reverseList = function (head) {
2
  if (head === null || head.next === null) {
3
    return head;
4
  }
5
  //这里的cur就是最后一个节点，也就是反转后的头节点
6
  const newHead = reverseList(head.next); // 反转后的头节点
7
  //这里请配合动画演示理解
8
  //如果链表是 1->2->3->4->5，那么此时的cur就是5
9
  //而head是4，head的下一个是5，下下一个是空
10
  //所以head.next.next 就是5->4
11
  head.next.next = head; // 将反转后的链表的尾结点与当前节点相连
12
  //防止链表循环，需要将head.next设置为空
13
  head.next = null;
14
  //每层递归函数都返回cur，也就是最后一个节点
15
  return newHead;
16
};
Copied!
复杂度分析
时间复杂度： O(n)O(n)O(n)
​
上述解法中，遍历了一次链表，这将耗费 O(n)O(n)O(n)
 的时间。
空间复杂度： O(n)O(n)O(n)
​
上述解法中，使用了递归的方法，这将耗费 O(n)O(n)O(n)
 的空间。
删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例
1
给定一个链表: 1->2->3->4->5, 和 n = 2.
2
​
3
当删除了倒数第二个节点后，链表变为 1->2->3->5.
Copied!
方法一 双指针法
思路
先用 first 指针前进 n，然后让 second 从 head 开始和 first 一起前进，直到 first 到了最后，此时 second 的下一个节点就是要删除的节点；如果 first 一开始前进 n 就已经不在链表中了，说明要删除的节点正是 head 节点，那么直接返回 head 的下一个节点。
详解
1.指针 first 指向头节点，然后，让其向后移动 n 步。
2.指针 second 指向头结点，并和 first 一起向后移动。当 first 的 next 指针为 null 时，second 即指向了要删除节点的前一个节点。
3.指针 first 的 next 指向要删除节点的下一个节点。
1
const removeNthFromEnd = (head, n) => {
2
  let first = head;
3
  let second = head;
4
  while (n > 0) {
5
    first = first.next;
6
    n -= 1;
7
  }
8
  if (!first) return head.next; // 如果first为null，则要删除的节点是首节点，直接返回head的下一个节点
9
  while (first.next) {
10
    first = first.next;
11
    second = second.next;
12
  }
13
  second.next = second.next.next;
14
  return head;
15
};
Copied!
复杂度分析
时间复杂度：O(n)O(n)O(n)
该算法对含有 nnn
 个结点的列表进行了单层遍历，因此，时间复杂度为 O(n)O(n)O(n)
​
空间复杂度：O(1)O(1)O(1)
 该算法只用了常量级的额外空间。故空间复杂度为 O(1)O(1)O(1)
​
方法二 单向链表成为双向链表
思路
可以遍历一次，让单向链表成为双向链表，先找到其尾节点，然后遍历整个链表同时n做递减操作，相当于从最后一个节点向前查找，直到n=1时，此时的节点就是我们要找的节点，然后直接删除即可。
详解
1.指针 cur 指向头节点，并定义 cur.prev、cur.next 使其成为双向链表。
2.找到其尾节点，当 cur.next 不存在时，则当前节点 cur 为尾节点。
3.遍历链表同时向前推进。n 做递减，当 n=1 时就是我们要删除的节点位置，否则，就让节点向前推进一个节点，直到 n=1 删除当前节点。（同时要考虑要删除的要删除的节点位置刚好是头节点的时候）
1
const removeNthFromEnd = (head, n) => {
2
  let cur = head;
3
  while (cur.next) {
4
    cur.next.prev = cur;
5
    cur = cur.next;
6
  }
7
  if (n === 1) {
8
    // 删除最后一个节点
9
    if (!cur.prev) { // 若是头节点则直接返回null
10
      return null;
11
    } else {
12
      cur.prev.next = null;
13
      return head;
14
    }
15
  }
16
  while (n > 0 && cur) {
17
    if (n === 1) {
18
      if (!cur.prev) {
19
        // 删除第一个节点
20
        cur.next.prev = null;
21
        return cur.next;
22
      } else {
23
        cur.prev.next = cur.next;
24
        cur.next.prev = cur.prev;
25
        return head;
26
      }
27
    }
28
    cur = cur.prev;
29
    n -= 1;
30
  }
31
};
Copied!
复杂度分析
时间复杂度：O(n)O(n)O(n)
 该算法对含有 nnn
 个结点的列表进行了单层遍历，因此，时间复杂度为 O(n)O(n)O(n)
。
空间复杂度：O(1)O(1)O(1)
 该算法只用了常量级的额外空间，因此，空间复杂度为 O(1)O(1)O(1)
。
合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
1
输入：1->2->4, 1->3->4
2
输出：1->1->2->3->4->4
Copied!
方法一 递归法
思路
用递归的方式，依次比较两个链表中首项的大小，保留数值小的为链表当前值，直到一个链表参数为空则结束。
详解
1.递归处理两个入参链表
2.若两个链表中有一个链表为空，则返回另一个链表
3.两个链表都不为空时比较两个链表中第一个节点的值，保留较小者（相同则均可）
4.继续递归执行去掉该节点的链表和另一个链表直至其中一个链表为空
代码
1
const mergeTwoLists = function (l1, l2) {
2
  if (l1 === null) {
3
    return l2;
4
  }
5
  if (l2 === null) {
6
    return l1;
7
  }
8
  if (l1.val <= l2.val) {
9
    l1.next = mergeTwoLists(l1.next, l2);
10
    return l1;
11
  } else {
12
    l2.next = mergeTwoLists(l1, l2.next);
13
    return l2;
14
  }
15
};
Copied!
复杂度分析
时间复杂度：O(n+m)O(n + m)O(n+m)
​
​nnn
 和 mmm
 分别是两个链表的长度，这将耗费 O(n+m)O(n + m)O(n+m)
 的时间。
空间复杂度：O(n+m)O(n + m)O(n+m)
​
每次比较值大小的时候，都会递归调用一次，耗费 O(1)O(1)O(1)
的栈空间，因此空间复杂度为 O(n+m)O(n + m)O(n+m)
​
方法二 双指针法
思路
创建一个新链表，通过判断两个链表当前值，将较小值放到新链表的下个节点，较小值的链表重新赋值为其下一节点，直到参数链表都为空时结束。
详解
1.创建一个新链表
2.当两个链表不都为空时执行以下循环
3.判断两个链表的第一个节点，取较小值放入新链表，原链表去掉该节点
4.直到两个链表都为空时循环结束，返回新链表
代码
1
const mergeTwoLists = function (l1, l2) {
2
  const prevHead = new ListNode(-1);
3
  let prevNode = prevHead;
4
  while (l1 !== null && l2 !== null) {
5
    if (l1.val <= l2.val) {
6
      prevNode.next = l1;
7
      l1 = l1.next;
8
    } else {
9
      prevNode.next = l2;
10
      l2 = l2.next;
11
    }
12
    prevNode = prevNode.next;
13
  }
14
  prevNode.next = l1 || l2;
15
  return prevHead.next;
16
};
Copied!
复杂度分析
时间复杂度：O(n+m)O(n + m)O(n+m)
​
​nnn
 和 mmm
 分别是两个链表的长度，时间复杂度为 O(n+m)O(n + m)O(n+m)
​
空间复杂度：O(1)O(1)O(1)
​
用申请了一个指针空间，其空间复杂度为 O(1)O(1)O(1)
。
两数相加
给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例
1
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
2
输出：7 -> 0 -> 8
3
原因：342 + 465 = 807
Copied!
方法一 游标法
思路
我们使用游标变量来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。
详解
1.设置游标变量 pointer1 和 pointer2，分别指向需要相加的两个链表 L1 和 L2 ；新建一个链表为 sumListNode，存储 L1 和 L2逐位相加的结果。
2.逐步移动 pointer1 和 pointer2，对 L1 和 L2 的每个节点相加得到两数之和 sumListNode 的链表节点
1
/**
2
 * Definition for singly-linked list.
3
 */
4
function ListNode (val) {
5
  this.val = val;
6
  this.next = null;
7
}
8
/**
9
 * @param {ListNode} l1
10
 * @param {ListNode} l2
11
 * @return {ListNode}
12
 */
13
const addTwoNumbers = function (l1, l2) {
14
  // 两数之和联表
15
  const sumListNode = new ListNode(0);
16
  // 指针1 指向 链表1
17
  let pointer1 = l1;
18
​
19
  // 指针2 指向 链表2
20
  let pointer2 = l2;
21
​
22
  // current 指向 两树之和的链表
23
  let current = sumListNode;
24
​
25
  // 逐位相加的进位
26
  let carry = 0;
27
​
28
  // 如果指针 pointer1、pointer2 还未移动结束
29
  while (pointer1 || pointer2) {
30
    // 如果 pointer1 已经移动到链表 l1 的末尾，当前值为0
31
    const num1 = pointer1 ? pointer1.val : 0;
32
​
33
    // 如果 pointer1 已经移动到链表 l1 的末尾，当前值为0
34
    const num2 = pointer2 ? pointer2.val : 0;
35
​
36
    // sum为当前移动位的两数之和
37
    const sum = carry + num1 + num2;
38
​
39
    // 存储进位
40
    carry = Math.floor(sum / 10);
41
​
42
    // sumListNode添加一个当前 l1 和 l2 相加的node ，值为 sum的个位数
43
    current.next = new ListNode(sum % 10);
44
​
45
    // current 指针后移一位
46
    current = current.next;
47
​
48
    // 如果 pointer1 未移动到 l1 的结尾，继续后移一位
49
    if (pointer1) {
50
      pointer1 = pointer1.next;
51
    }
52
     // 如果 pointer2 未移动到 l2 的结尾，继续后移一位
53
    if (pointer2) {
54
      pointer2 = pointer2.next;
55
    }
56
  }
57
  // 如果有进位，两数之和的联表，加一个进位的 node
58
  if (carry > 0) {
59
    current.next = new ListNode(carry);
60
  }
61
​
62
  return sumListNode.next;
63
};
Copied!
复杂度分析
时间复杂度： O(n)O(n)O(n)
​
假设 mmm
 和 nnn
 分别表示 L1L1L1
 和 L2L2L2
 的长度，上面的算法最多重复 max(m,n)max(m, n)max(m,n)
 次。
空间复杂度： O(n)O(n)O(n)
​
新列表的长度最多为 max(m,n)max(m, n)max(m,n)
 。
方法二 数字相加法
思路
本题目为链表模拟的两个数字相加，那么可以现将链表转换为数字，数字相加，最后把结果转换为链表。由于javascript 数字范围为 [−253,253][-2^{53}, 2^{53}][−253,253]
 ，考虑存在过大的数字相加，此处数字使用BigInt类型 https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt。​
详解
两数相加： 1. 将 L1 转换为数字 num1，将 L2 转换为数字 num2， 2. 将数字 num1 和 num2 相加得出两数之和 sumNum 3. 最后将 sumNum 转换为链式结构
1
/**
2
 * Definition for singly-linked list.
3
 */
4
function ListNode (val) {
5
  this.val = val;
6
  this.next = null;
7
}
8
/**
9
 * @description 将链表转换为数字
10
 * @param {ListNode} listNode
11
 * @return {BigInt}
12
 */
13
const listNodeToNum = function (listNode) {
14
  let numString = '';
15
  let currentNode = listNode;
16
  while (currentNode) {
17
    numString = currentNode.val + numString;
18
    currentNode = currentNode.next;
19
  }
20
  // eslint-disable-next-line no-undef
21
  return BigInt(numString);
22
};
23
​
24
/**
25
 * @description 数字转为链表
26
 * @param {number} num 数字
27
 * @return {ListNode}
28
 */
29
const numToListNode = function (num) {
30
  let listNode = null;
31
  const numString = num.toString();
32
  for (let i = 0; i < numString.length; i++) {
33
    const newNode = new ListNode(numString[i]);
34
    newNode.next = listNode;
35
    listNode = newNode;
36
  }
37
  return listNode;
38
};
39
​
40
const addTwoNumbers = function (l1, l2) {
41
  return numToListNode(listNodeToNum(l1) + listNodeToNum(l2));
42
};
Copied!
复杂度分析
时间复杂度： O(n)O(n)O(n)
​
空间复杂度： O(n)O(n)O(n)
​