跳到主要内容

单链表操作

题一、判断链表中是否有环​

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

进阶: 你能用 O(1)（即，常量）内存解决此问题吗？

示例1:

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例2:

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

方案A、哈希表​

思路: 遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。具体来讲,我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。

实现

function hasCycle(head){
  const set = new Set();
  while(head != null){
    if(set.has(head)){
      return true;
    }
    set.add(head);
    head = head.next;
  }
  return false;
}

方案B、快慢指针​

思路: 使用快慢指针法， 分别定义 fast 和 slow 指针。从头结点出发,fast指针每次移动两个节点,slow指针每次移动一个节点。如果 fast 和 slow 指针在途中相遇 ，说明这个链表有环。

function hasCycle(head){
  let fast=head;
  let slow=head;
  while(fast&&fast.next){
    slow=slow.next;
    fast=fast.next.next;
    if(slow==fast){
      return true
    }
  }
  return false
}

性能分析:

  • 时间复杂度：O(N)，其中 N 是链表中的节点数。

    • 当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。
    • 当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N 轮。

  • 空间复杂度：O(1)。我们只使用了两个指针的额外空间。

题二、链表中环的入口结点​

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明:不允许修改给定的链表。

进阶:你是否可以使用 O(1) 空间解决此题？

示例1:

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例2:

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

方案A、哈希表​

思路

遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现。

实现

function detectCycle(head){
  const set = new Set();
  while(head != null){
    if(set.has(head)){
      return head;
    } 
    set.add(head);
    head = head.next;
  }
  return null;
}

方案B、快慢指针​

思路

使用两个指针, fast 与 slow。它们起始都位于链表的头部。随后,slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。如下图所示，设链表中环外部分的长度为 a。slow 指针进入环后，又走了 b 的距离与 fast 相遇。此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc。

Preview

根据题意，任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。因此，我们有 a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)。有了 a=c+(n-1)(b+c)a=c+(n−1)(b+c) 的等量关系，我们会发现: 从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。

实现

function detectCycle(head){
  if(head == null){
    return null;
  }
  let slow = head;
  let fast = head;
  while(fast != null){
    slow = slow.next;
    if(fast.next != null){
      fast = fast.next.next;
    }else{
      return null;
    }
    if(fast === slow){
      let ptr = head;
      while(ptr !== slow){
        ptr = ptr.next;
        slow = slow.next;
      }
      return ptr;
    }
  }
  return null;
}

题三、合并两个有序链表​

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

示例1

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例2

输入：l1 = [], l2 = []
输出：[]

方案A、递归​

思路

  • 如果 l1 和 l2 为空链表，没有任何操作需要合并
  • 判断 l1 和 l2 哪一个链表的值更小，然后递归地决定下一个添加到结果里的节点。
  • 如果两个链表有一个为空，递归结束。

实现

function mergeTwoLists(listA, listB) {
  if (listA === null) {
    return listB;
  } else if (listB === null) {
    return listA;
  } else if (listA.val < listB.val) {
    listA.next = mergeTwoLists(listA.next, listB);
    return listA;
  } else {
    listB.next = mergeTwoLists(listA, listB.next);
    return listB;
  }
}

性能分析:

时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 O(n+m)。

空间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+mn+m 次，因此空间复杂度为 O(n+m)。

方案B、迭代​

思路

当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。

实现

function mergeTwoLists(listA,listB){
  if(listA == null || listB == null){
    return listA == null ? listB : listA;
  }
  const prevHead = new ListNode(-1);
  let prev = prevHead;
  while(listA != null && listB != null){
    if(listA.val <= listB.val){
      prev.next = listA;
      listA = listA.next;
    }else{
      prev.next = listB;
      listB = listB.next;
    }
    prev = prev.next;
  }
  prev.next = listA == null ? listB : listA;
  return prevHead.next;
}

性能分析:

时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)。

空间复杂度：O(1)。我们只需要常数的空间存放若干变量。

题四、合并K个升序链表​

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例一

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例二

输入：lists = []
输出：[]

方案A、顺序合并​

function mergeTwoLists(listA,listB){
  if(listA == null || listB == null){
    return listA == null ? listB : listA;
  }
  const prevHead = new ListNode(-1);
  let prev = prevHead;
  while(listA != null && listB != null){
    if(listA.val <= listB.val){
      prev.next = listA;
      listA = listA.next;
    }else{
      prev.next = listB;
      listB = listB.next;
    }
    prev = prev.next;
  }
  prev.next = listA == null ? listB : listA;
  return prevHead.next;
}
function mergeKLists(lists){
  let result = null;
  for(let i=0;i<lists.length;i++){
    result = mergeTwoLists(result,lists[i]);
  }
  return result;
}

方案B、分治合并​

function mergeTwoLists(listA,listB){
  if(listA == null || listB == null){
    return listA == null ? listB : listA;
  }
  const prevHead = new ListNode(-1);
  let prev = prevHead;
  while(listA != null && listB != null){
    if(listA.val <= listB.val){
      prev.next = listA;
      listA = listA.next;
    }else{
      prev.next = listB;
      listB = listB.next;
    }
    prev = prev.next;
  }
  prev.next = listA == null ? listB : listA;
  return prevHead.next;
}
function merge(lists,left,right){
  if(left == right){
    return lists[left]
  }
  if(left > right){
    return null;
  }
  let middle = (left + right) >> 1;
  return mergeTwoLists(merge(lists,left,middle),merge(lists,middle+1,right));
}
function mergeKLists(lists){
  return merge(lists,0,lists.length-1);
}

方案C、使用优先队列合并​

class PriorityQueue {
  constructor() {
    this.length = 0;
    this.data = [];
  }
  compareTo(a, b) {
    return a.val - b.val;
  }
  shiftUp(index) {
    while (index > 0) {
      let parent = Math.floor((index - 1) / 2);
      if (this.compareTo(this.data[index], this.data[parent]) < 0) {
        [this.data[index], this.data[parent]] = [
          this.data[parent],
          this.data[index],
        ];
        index = parent;
      } else {
        return;
      }
    }
  }
  shiftDown(index) {
    while (index * 2 + 1 <= this.length - 1) {
      let child = index * 2 + 1;
      if (
        child + 1 <= this.length - 1 &&
        this.compareTo(this.data[child], this.data[child + 1]) > 0
      ) {
        child++;
      }
      if (this.compareTo(this.data[index], this.data[child]) > 0) {
        [this.data[index], this.data[child]] = [
          this.data[child],
          this.data[index],
        ];
        index = child;
      } else {
        return;
      }
    }
  }
  add(value) {
    this.data.push(value);
    this.length++;
    if (this.length != 1) {
      this.shiftUp(this.length - 1);
    }
  }
  poll() {
    const result = this.data[0];
    if (this.length == 1) {
      this.data.pop();
    } else {
      this.data[0] = this.data.pop();
    }
    this.length--;
    this.shiftDown(0);
    return result;
  }
  peek() {
    return this.data[0];
  }
  isEmpty() {
    return this.data.length === 0;
  }
}

class Status {
  constructor(val, node) {
    this.val = val;
    this.node = node;
  }
}

const queue = new PriorityQueue();

function mergeKLists(lists) {
  for (let item of lists) {
    if (item != null) {
      queue.add(new Status(item.val, item));
    }
  }
  let prevHead = new ListNode(-1);
  let prev = prevHead;
  while (!queue.isEmpty()) {
    const status = queue.poll();
    prev.next = status.node;
    prev = prev.next;
    if (status.node.next != null) {
      queue.add(new Status(status.node.next.val, status.node.next));
    }
  }
  return prevHead.next;
}

题五、反转链表​

方案A、递归​

方式一: 头递归法

  • 思路: 核心思想就是从当前链表的头结点开始，依次向后遍历。遍历过程依次改变各节点的 next 指向，即另其指向前一个节点。

  • 过程:

    1. head -> head.next 这两个节点反转时： head.next.next=head; head.next=null 就好了 , 但是如果直接改变节点.next , 那么会找不到下一个节点，所以，进行下面的操作。
    2. 通过 next 保存 节点.next 
    3. 通过 prev 保存 节点的上一个节点
    3. 反转的关键就是将节点的 next 指向 prev

  • 实现

    function reverseList(head){
        const reverse = (prev,current)=>{
            if(!current){
                return prev;
            }
            let next = current.next;
            current.next = prev;
            return reverse(current,next);
        }
        return reverse(null,head);
    }

方式二: 尾递归法

  • 思路: 核心思想是从当前链表的尾节点开始，依次向前遍历，遍历过程依次改变各节点的 next 指向，即另其指向前一个节点。

  • 过程:

    1. head -> head.next 这两个节点反转时： head.next.next=head; head.next=null 就好了
    2. 但是如果直接改变了 head.next.next ，那么找不到下一个节点了，所以通过从后往前的方式
    3. 从后往前的方式采用递归找到最后一个节点

  • 实现:

    function reverseList(head){
        const reverse = (current)=>{
            if(!current || !current.next){
                return current;
            }
            let prev = reverse(current.next);
            current.next.next = current;
            current.next = null;
            return prev;
        }
        return reverse(head);
    }

方案B、迭代​

方式一: 三指针迭代法

  • 思路: 核心思想就是从当前链表的头结点开始，依次向后遍历。遍历过程依次改变各节点的 next 指向，即另其指向前一个节点。

  • 过程:

    通过一个变量保存 next : 由于链表的特性，如果直接将节点的 next 改变为上一个节点，那么下一个节点就无法找到了，所以需要通过一个变量来保存节点的 next 指向，然后改变节点的 next 指向

    通过一个变量保存 prev : 由于链表的特性，每一个节点只知道自己的下一个节点，不知道自己的上一个节点，所以需要一个变量来保存当前节点的上一个节点

  • 实现:

    function reverseList(head){
        if(!head || !head.next){
            return head;
        }
        let prev = null;
        let next = null;
        let current = head;
        while(current){
            let next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }

方式二:双指针迭代法-头插法

  • 思路: 基于三指针迭代法，将 头指针 充当 next 指针即可

  • 实现:

    function reverseList(head){
        if(!head || !head.next){
            return head;
        }
        let prev = null;
        let current = null;
        while(head){
            current = head;
            head = head.next;
            current.next = prev;
            prev = current;
        }
        return prev;
    }

方式三: 双指针法-就地逆置法

  • 思路: 基于三指针迭代法，将 头指针 充当 prev 即可

  • 实现:

    function reverseList(head){
        if(!head || !head.next){
            return head;
        }
        let next = head.next;
        let current = head;
        while(next){
            current.next = next.next;
            next.next = head;
            head = next;
            next = current.next;
        }
        return head;
    }

题六、链表内指定区间反转​

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

方案A、两次遍历【穿针引线】​

思路

  1. 找到left所在节点的前驱节点precursor,找到right所在节点rightNode,后继节点为successor

  2. 以[leftNode,rightNode]为区间进行反转-反转方法随意

  3. 拼接反转结果-precursor拼接反转之后链表的头结点,反转之后链表的尾节点拼接successor

实现

function reverseList(head){
  if(!head || !head.next){
    return head;
  }
  let next = head.next;
  let current = head;
  while(next){
    current.next = next.next;
    next.next = head;
    head = next;
    next = current.next;
  }
}
function reverseBetween(head,left,right){
  const dummyNode = new ListNode(-1);
  dummyNode.next = head;
  let precursor = dummyNode;
  for(let i=0;i<left-1;i++){
    precursor = precursor.next;
  }
  let rightNode = precursor;
  for(let i=0;i<right-left+1;i++){
    rightNode = rightNode.next;
  }
  let leftNode = precursor.next;
  let successor = rightNode.next;
  precursor.next = null;
  rightNode.next = null;
  reverseList(leftNode);
  precursor.next = rightNode;
  leftNode.next = successor;
  return dummyNode.next;
}

方案B、一次遍历【穿针引线】​

思路: 在待反转的区间里，每次遍历到一个节点，让这个节点来到反转的起始部分。

  1. 找到待反转区间起始节点的前驱结点precursor,current 指向待反转区间的起始节点precursor.next
  2. next 节点永远指向current的下一个节点

实现

function reverseBetween(head,left,right){
    let dummyNode =  new ListNode(-1);
    dummyNode.next = head;
    let precursor = dummyNode;
    for(let i=0; i<left-1; i++){
        precursor = precursor.next;
    }
    let next = null;
    let current = precursor.next;
    for(let i=0; i<right-left; i++){
        next = current.next;
        current.next = next.next;
        next.next = precursor.next;
        precursor.next = next;
    }
    return dummyNode.next;
}

题七、K 个一组翻转链表​

给你链表的头节点 head,每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

方案A 模拟​

function reverse(head, tail) {
  let prev = tail.next;
  let current = head;
  while (prev !== tail) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return [tail, head];
}
function reverseKGroup(head, k) {
  const dummyHead = new ListNode(0);
  dummyHead.next = head;
  let prev = dummyHead;
  while (head) {
    let tail = prev;
    for (let i = 0; i < k; i++) {
      tail = tail.next;
      if (!tail) {
        return dummyHead.next;
      }
    }
    const next = tail.next;
    [head, tail] = reverse(head, tail);
    prev.next = head;
    tail.next = next;
    prev = tail;
    head = tail.next;
  }
  return dummyHead.next;
}

题八、查找倒数第 k 个节点​

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

方案A、双指针​

思路

快慢指针的思想。我们将第一个指针fast指向链表的第k + 1个节点，第二个指针slow指向链表的第一个节点，此时指针fast与slow二者之间刚好间隔k个节点。此时两个指针同步向后走，当第一个指针fast走到链表的尾部空节点时，则此时slow指针刚好指向链表的倒数第k个节点。

实现

function getKthFromEnd(head,k){
    let fast = head;
    let slow = head;
    while(fast && k>0){
        k = k-1;
        fast = fast.next;
    }
    while(fast){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

题九、删除倒数第 k 个节点​

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例1

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

实例2

输入：head = [1], n = 1
输出：[]

方案A、栈​

思路

在遍历链表的同时将所有节点依次入栈。根据栈先进后出的原则，我们弹出栈的第n个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。这样一来，删除操作就变得十分方便了。

实现

function removeNthFromEnd(head,n){
  let dummy = new ListNode(0,head);
  let first = head;
  let second = dummy;
  while(first != null && n>0){
      n = n-1;
      first = first.next;
  }
  while(first){
      first = first.next;
      second = second.next;
  }
  second.next = second.next.next;
  return dummy.next;
}

方案B、双指针​

思路

初始时first和second均指向头节点。我们首先使用first对链表进行遍历，遍历的次数为n。此时，first 和second之间间隔了n−1个节点，即first比second超前了n个节点。在这之后，我们同时使用first和second对链表进行遍历。当first遍历到链表的末尾（即first为空指针）时，second恰好指向倒数第n个节点。

如果我们能够得到的是倒数第n个节点的前驱节点而不是倒数第n个节点的话，删除操作会更加方便。因此我们可以考虑在初始时将second指向哑节点，其余的操作步骤不变。这样一来，当first遍历到链表的末尾时，second的下一个节点就是我们需要删除的节点。

实现

function removeNthFromEnd(head,n){
  let dummy = new ListNode(0,head);
  let first = head;
  let second = dummy;
  while(first && n>0){
    n = n-1;
    first = first.next;
  }
  while(first){
    first = first.next;
    second = second.next;
  }
  second.next = second.next.next;
  let result = dummy.next;
  return result;
}

题十、两个链表的第一个公共节点​

输入两个链表，找出它们的第一个公共节点。

示例1

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例2

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

方案A、哈希表​

思路

判断两个链表是否相交，可以使用哈希集合存储链表节点。首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中:

  • 如果当前节点不在哈希集合中，则继续遍历下一个节点；

  • 如果当前节点在哈希集合中，则后面的节点都在哈希集合中，即从当前节点开始的所有节点都是两个链表的公共节点，因此在链表 headB 中遍历到的第一个在哈希集合中的节点就是两个链表的第一个公共节点，返回该节点。

  • 如果链表 headB 中的所有节点都不在哈希集合中，则两个链表不相交，返回 null。

实现

function getIntersectionNode(headA,headB){
  const set = new Set();
  let current = headA;
  while(current != null){
    set.add(current);
    current = current.next;
  }
  current = headB;
  while(current != null){
    if(set.has(current)){
      return current
    }
    current = current.next;
  }
  return null;
}

方案B、双指针​

思路

只有当链表 headA 和 headB 都不为空时，两个链表才可能相交。因此首先判断链表 headA 和 headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。当链表 headA 和 headB 都不为空时，创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下:

  • 每步操作需要同时更新指针 pA 和 pB

  • 如果指针 pA 不为空，则将指针 pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点

  • 如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点

  • 当指针 pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null

实现

function getIntersectionNode(headA,headB){
  if(headA == null || headB == null){
    return null;
  }
  let pA = headA;
  let pB = headB;
  while(pA != pB){
    pA = pA == null ? headB : pA.next;
    pB = pB == null ? headA : pB.next;
  }
  return pA;
}

题十一、链表中的两数相加​

给定两个 非空链表 l1 和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例1:

  l1: 7 2 4 3
  l2:   5 6 4
 结果: 7 8 0 7

方案A、栈​

思路: 本题的主要难点在于链表中数位的顺序与我们做加法的顺序是相反的，为了逆序处理所有数位，我们可以使用栈：把所有数字压入栈中，再依次取出相加。计算过程中需要注意进位的情况

实现

function addTwoNumbers(l1, l2) {
  const stack1 = [];
  const stack2 = [];
  while (l1 != null) {
    stack1.push(l1.val);
    l1 = l1.next;
  }
  while (l2 != null) {
    stack2.push(l2.val);
    l2 = l2.next;
  }
  let carry = 0;
  let result = null;
  while (stack1.length || stack2.length || carry != 0) {
    let a = stack1.length === 0 ? 0 : stack1.pop();
    let b = stack2.length === 0 ? 0 : stack2.pop();
    let current = a + b + carry;
    carry = (current / 10) >>> 0;
    current %= 10;
    let currentNode = new ListNode(current);
    currentNode.next = result;
    result = currentNode;
  }
  return result;
}

题十二、链表排序​

给定链表的头结点 head，请将其按升序排列并返回 排序后的链表。

示例1

4 2 1 3
1 2 3 4

方案A、自顶向下归并排序​

思路: 对链表自顶向下归并排序的过程如下:

  1. 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动2步，慢指针每次移动1步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。

  2. 对两个子链表分别排序。

  3. 将两个排序后的子链表合并，得到完整的排序后的链表。

上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于1，即当链表为空或者链表只包含1个节点时，不需要对链表进行拆分和排序。

实现

function merge(head1, head2) {
  const dummyHead = new ListNode(0);
  let temp = dummyHead;
  let temp1 = head1;
  let temp2 = head2;
  while (temp1 !== null && temp2 !== null) {
    if (temp1.val <= temp2.val) {
      temp.next = temp1;
      temp1 = temp1.next;
    } else {
      temp.next = temp2;
      temp2 = temp2.next;
    }
    temp = temp.next;
  }
  if (temp1 !== null) {
    temp.next = temp1;
  } else if (temp2 !== null) {
    temp.next = temp2;
  }
  return dummyHead.next;
}

function toSortList(head, tail) {
  if (head === null) {
    return head;
  }
  if (head.next === tail) {
    head.next = null;
    return head;
  }
  let slow = head;
  let fast = head;
  while (fast !== tail) {
    slow = slow.next;
    fast = fast.next;
    if (fast !== tail) {
      fast = fast.next;
    }
  }
  const middle = slow;
  return merge(toSortList(head, middle), toSortList(middle, tail));
}

function sortList(head) {
  return toSortList(head, null);
}

方案B、自底向上归并排序​

思路: 使用自底向上的方法实现归并排序，则可以达到 O(1) 的空间复杂度。首先求得链表的长度 length，然后将链表拆分成子链表进行合并。具体做法如下:

  1. 用 subLength 表示每次需要排序的子链表的长度，初始时 subLength=1。

  2. 每次将链表拆分成若干个长度为 subLength 的子链表（最后一个子链表的长度可以小于 subLength），按照每两个子链表一组进行合并，合并后即可得到若干个长度为 subLength×2 的有序子链表（最后一个子链表的长度可以小于 subLength×2）。

    • 正常写法: subLength *= 2
    • 位运算写法: subLength <<= 1

  3. 将 subLength 的值加倍，重复第 2 步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于 length，整个链表排序完毕。

实现:

function merge(head1, head2) {
  const dummyHead = new ListNode(0);
  let temp = dummyHead;
  let temp1 = head1;
  let temp2 = head2;
  while (temp1 !== null && temp2 !== null) {
    if (temp1.val <= temp2.val) {
      temp.next = temp1;
      temp1 = temp1.next;
    } else {
      temp.next = temp2;
      temp2 = temp2.next;
    }
    temp = temp.next;
  }
  if (temp1 !== null) {
    temp.next = temp1;
  } else if (temp2 !== null) {
    temp.next = temp2;
  }
  return dummyHead.next;
}

function sortList(head) {
  if (head === null) {
    return head;
  }
  let length = 0;
  let node = head;
  while (node !== null) {
    length++;
    node = node.next;
  }
  const dummyHead = new ListNode(0, head);
  for (let subLength = 1; subLength < length; subLength <<= 1) {
    let prev = dummyHead;
    let curr = dummyHead.next;
    while (curr !== null) {
      let head1 = curr;
      for (let i = 1; i < subLength && curr.next !== null; i++) {
        curr = curr.next;
      }
      let head2 = curr.next;
      curr.next = null;
      curr = head2;
      for (
        let i = 1;
        i < subLength && curr !== null && curr.next !== null;
        i++
      ) {
        curr = curr.next;
      }
      let next = null;
      if (curr != null) {
        next = curr.next;
        curr.next = null;
      }
      const merged = merge(head1, head2);
      prev.next = merged;
      while (prev.next !== null) {
        prev = prev.next;
      }
      curr = next;
    }
  }
  return dummyHead.next;
}

题十三、回文链表​

给定一个链表的 头节点 head ，请判断其是否为回文链表。如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例:

1 2 3 3 2 1

方案A、快慢指针​

思路: 我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。整个流程可以分为以下五个步骤:

  1. 找到前半部分链表的尾节点, 我们可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。若链表有奇数个节点，则中间的节点应该看作是前半部分。

  2. 反转后半部分链表

  3. 判断是否回文

  4. 恢复链表

  5. 返回结果

实现

function reverseList(head) {
  let prev = null;
  let curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}
function endOfFirstHalf(head) {
  let fast = head;
  let slow = head;
  while (fast.next !== null && fast.next.next !== null) {
    fast = fast.next.next;
    slow = slow.next;
  }
  return slow;
}
function isPalindrome(head){
  if(head === null){
    return true;
  }
  const firstHalfEnd = endOfFirstHalf(head);
  const secondHalfStart = reverseList(firstHalfEnd.next);
  let p1 = head;
  let p2 = secondHalfStart;
  let result = true;
  while(result && p2 !== null){
    if(p1.val !== p2.val){
      result = false;
    }
    p1 = p1.next;
    p2 = p2.next;
  }
  firstHalfEnd.next = reverseList(secondHalfStart);
  return result;
}

题十四、奇偶链表​

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例1:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例2:

输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL

方案A、分离节点后合并​

思路: 对于原始链表，每个节点都是奇数节点或偶数节点。头节点是奇数节点，头节点的后一个节点是偶数节点，相邻节点的奇偶性不同。因此可以将奇数节点和偶数节点分离成奇数链表和偶数链表，然后将偶数链表连接在奇数链表之后，合并后的链表即为结果链表。

  • 定义奇偶头结点: 奇节点头结点就是原链表头结点，偶节点头结点为原链表头结点的下一个节点
    • head
    • evenHead: head.next
  • 定义两个指针:
    • odd: 奇节点中间节点
    • even: 偶节点中间节点
  • 进行分离合并
    • 奇数节点的后一个节点为偶数节点的下一个节点
    • 偶数节点的后一个节点为奇数节点的下一个节点
oddEvenList = function(head) {
    if(!head){
        return head;
    }
    let evenHead=head.next;
    let odd=head;
    let even=evenHead;
    while(even&&even.next){
        odd.next=even.next;
        odd=odd.next;
        even.next=odd.next;
        even=even.next;
    }
    odd.next=evenHead;
    return head;
};

性能分析:

时间复杂度：O(n)，其中 n 是链表的节点数。需要遍历链表中的每个节点，并更新指针。

空间复杂度：O(1)。只需要维护有限的指针。

题十五、删除排序链表中的重复元素-I​

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例1:

输入：head = [1,1,2]
输出：[1,2]

方案A、一次遍历​

思路: 由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。具体地，我们从指针 cur 指向链表的头节点，随后开始对链表进行遍历。如果当前 cur 与 cur.next 对应的元素相同，那么我们就将 cur.next 从链表中移除；否则说明链表中已经不存在其它与 cur 对应的元素相同的节点，因此可以将 cur 指向 cur.next。当遍历完整个链表之后，我们返回链表的头节点即可。

细节: 当我们遍历到链表的最后一个节点时，cur.next 为空节点，如果不加以判断，访问 cur.next 对应的元素会产生运行错误。因此我们只需要遍历到链表的最后一个节点，而不需要遍历完整个链表。

实现

function deleteDuplicates(head) {
  if (!head) {
    return head;
  }
  let curr = head;
  while (curr.next) {
    if (curr.val === curr.next.val) {
      curr.next = curr.next.next;
    } else {
      curr = curr.next;
    }
  }
  return head;
}

题十六、除排序链表中的重复元素 II​

给定一个已排序的链表的头 head, 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回已排序的链表。

示例1:

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

方案A、一次遍历​

思路: 由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。由于链表的头节点可能会被删除，因此我们需要额外使用一个哑节点（dummy node）指向链表的头节点。具体地，

  1. 我们从指针 cur 指向链表的哑节点，随后开始对链表进行遍历。

  2. 如果当前 cur.next 与 cur.next.next 对应的元素相同，那么我们就需要将 cur.next 以及所有后面拥有相同元素值的链表节点全部删除。我们记下这个元素值 x，随后不断将 cur.next 从链表中移除，直到 cur.next 为空节点或者其元素值不等于 x 为止。此时，我们将链表中所有元素值为 x 的节点全部删除。

  3. 当遍历完整个链表之后，我们返回链表的的哑节点的下一个节点 dummy.next 即可

  4. 需要注意 cur.next 以及 cur.next.next 可能为空节点，如果不加以判断，可能会产生运行错误。

实现

function deleteDuplicates(head) {
  if (!head) {
    return head;
  }
  const dummy = new ListNode(0, head);
  let curr = dummy;
  while (curr.next && curr.next.next) {
    if (curr.next.val === curr.next.next.val) {
      const val = curr.next.val;
      while (curr.next && curr.next.val == val) {
        curr.next = curr.next.next;
      }
    } else {
      curr = curr.next;
    }
  }
  return dummy.next;
}

题十七、相交链表​

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

通过双指针​

思路:

  • 求得 headA 和 headB 的长度，获取两个链表的差值
  • 移动长度较长链表至长度较短链表的开头位置，此时两链表移动指针对齐
  • 两指针比较是否相同，如果相同，当前移动指针即为所求的交点
function getLinkedListLen(head){
    let len=0;
    let current=head;
    while(current){
        current=current.next;
        len++;
    }
    return len;
}
function getIntersectionNode(headA, headB) {
    let lenA=getLinkedListLen(headA);
    let lenB=getLinkedListLen(headB);
    let currentA=headA;
    let currentB=headB;
    if(lenA<lenB){
        [lenA,lenB]=[lenB,lenA];
        [currentA,currentB]=[currentB,currentA];
    }
    let len=lenA-lenB;
    while(len-->0){
        currentA=currentA.next;
    }
    while(currentA&&currentA!=currentB){
        currentA=currentA.next;
        currentB=currentB.next;
    }
    return currentA;
};

性能分析:

时间复杂度：O(m+n)，其中 m 和 n 是分别是链表 headA 和 headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。

空间复杂度：O(1)。

题十八、移除链表元素​

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例1:

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例2:

输入：head = [], val = 1
输出：[]

示例3:

输入：head = [7,7,7,7], val = 7
输出：[]

方案A 递归​

function removeElements(head, val) {
    if(!head){
        return head
    }
    head.next=removeElements(head.next,val);
    return head.val==val?head.next:head;
};

性能分析:

时间复杂度：O(n)，其中 n 是链表的长度。递归过程中需要遍历链表一次。

空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用栈，最多不会超过 n 层。

方案B 迭代​

思路:设置虚拟头结点，就不用考虑删除头结点和非头结点的情况，按照统一的方式进行删除即可。

function removeElements(head, val) {
    let dummyHead=new ListNode(0,head);
    let current=dummyHead;
    while(current.next){
          if(current.next.val==val){
              current.next=current.next.next;
          }else{
              current=current.next;
          }
    }
    return dummyHead.next;
};

性能分析:

时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。

空间复杂度：O(1)。

题十九、链表的中间结点​

给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

示例1:

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例2:

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

方案A、快慢指针​

思路: 用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。

实现

function middleNode(head){
  let fast = head;
  let slow = head;
  while(fast !== null && fast.next !== null){
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

题二十、重排链表​

给定一个单链表 L 的头节点 head , 单链表 L 表示为:

L0 → L1 → … → Ln-1 → Ln

请将其重新排列后变为:

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例1:

输入: head = [1,2,3,4]
输出: [1,4,2,3]

方案A、寻找链表中点 + 链表逆序 + 合并链表​

思路: 注意到目标链表即为将原链表的左半端和反转后的右半端合并后的结果。这样我们的任务即可划分为三步:

  1. 找到原链表的中点

  2. 将原链表的右半端反转

  3. 将原链表的两端合并

实现

function reverseList(head) {
  let next = null;
  let prev = null;
  let current = head;
  while (current != null) {
    next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return prev;
}
function middleNode(head) {
  let fast = head;
  let slow = head;
  while (fast.next !== null && fast.next.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}
function mergeList(l1, l2) {
  let l1Temp;
  let l2Temp;
  while (l1 !== null && l2 !== null) {
    l1Temp = l1.next;
    l2Temp = l2.next;
    l1.next = l2;
    l1 = l1Temp;
    l2.next = l1;
    l2 = l2Temp;
  }
}
function reorderList(head) {
  if (head == null) {
    return;
  }
  let middle = middleNode(head);
  let l1 = head;
  let l2 = middle.next;
  middle.next = null;
  l2 = reverseList(l2);
  mergeList(l1, l2);
}

题二十一、合并排序链表​

给定一个链表数组，每个链表都已经按升序排列。请将所有链表合并到一个升序链表中，返回合并后的链表。

示例一:

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

方案A、分治合并、​

思路:

  1. 将 k 个链表配对并将同一对中的链表合并

  2. 第一轮合并以后， k 个链表被合并成了 k/2 个链表，平均长度为 2n/k ; 然后是 k/4 个链表, k/8个链表 ​

  3. 重复这一过程，直到我们得到了最终的有序链表。

实现

function mergeTwoLists(l1, l2) {
  if (l1 === null || l2 === null) {
    return l1 === null ? l2 : l1;
  }
  let head = new ListNode(0);
  let tail = head;
  let l1Ptr = l1;
  let l2Ptr = l2;
  while (l1Ptr !== null && l2Ptr !== null) {
    if (l1Ptr.val < l2Ptr.val) {
      tail.next = l1Ptr;
      l1Ptr = l1Ptr.next;
    } else {
      tail.next = l2Ptr;
      l2Ptr = l2Ptr.next;
    }
    tail = tail.next;
  }
  tail.next = l1Ptr !== null ? l1Ptr : l2Ptr;
  return head.next;
}
function merge(lists, l, r) {
  if (l === r) {
    return lists[l];
  }
  if (l > r) {
    return null;
  }
  let middle = (l + r) >> 1;
  return mergeTwoLists(merge(lists, l, middle), merge(lists, middle + 1, r));
}
function mergeKLists(lists) {
  return merge(lists, 0, lists.length - 1);
}

方案B、使用优先队列合并​

思路: 我们需要维护当前每个链表没有被合并的元素的最前面一个，k 个链表就最多有 k 个满足这样条件的元素，每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，我们可以用优先队列来优化这个过程。

实现

class Status {
  constructor(val, ptr) {
    this.val = val;
    this.ptr = ptr;
  }
}

class MinHeap {
  constructor() {
    this.length = 0;
    this.data = [];
  }
  compareTo(a, b) {
    return a.val - b.val;
  }
  shiftUp(index) {
    while (index > 0) {
      let parent = Math.floor((index - 1) / 2);
      if (this.compareTo(this.data[index], this.data[parent]) < 0) {
        [this.data[index], this.data[parent]] = [
          this.data[parent],
          this.data[index],
        ];
        index = parent;
      } else {
        return;
      }
    }
  }
  shiftDown(index) {
    while (index * 2 + 1 <= this.length - 1) {
      let child = index * 2 + 1;
      if (
        child + 1 <= this.length - 1 &&
        this.compareTo(this.data[child], this.data[child + 1]) > 0
      ) {
        child++;
      }
      if (this.compareTo(this.data[index], this.data[child]) > 0) {
        [this.data[index], this.data[child]] = [
          this.data[child],
          this.data[index],
        ];
        index = child;
      } else {
        return;
      }
    }
  }
  add(value) {
    this.data.push(value);
    this.length++;
    if (this.length != 1) {
      this.shiftUp(this.length - 1);
    }
  }
  poll() {
    const result = this.data[0];
    if (this.length == 1) {
      this.data.pop();
    } else {
      this.data[0] = this.data.pop();
    }
    this.length--;
    this.shiftDown(0);
    return result;
  }
  peek() {
    return this.data[0];
  }
  isEmpty() {
    return this.data.length === 0;
  }
}

function mergeKLists(lists) {
  const queue = new MinHeap();
  for (let node of lists) {
    if (node != null) {
      queue.add(new Status(node.val, node));
    }
  }
  let head = new ListNode(0);
  let tail = head;
  while (!queue.isEmpty()) {
    let status = queue.poll();
    tail.next = status.ptr;
    tail = tail.next;
    if (status.ptr.next !== null) {
      queue.add(new Status(status.ptr.next.val, status.ptr.next));
    }
  }
  return head.next;
}

题二十二、复杂链表的复制​

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例一:

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例二:

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例三:

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

方案A、回溯 + 哈希表​

思路:

本题要求我们对一个特殊的链表进行深拷贝。如果是普通链表，我们可以直接按照遍历的顺序创建链表节点。而本题中因为随机指针的存在，当我们拷贝节点时，「当前节点的随机指针指向的节点」可能还没创建，因此我们需要变换思路。一个可行方案是，我们利用回溯的方式，让每个节点的拷贝操作相互独立。对于当前节点，我们首先要进行拷贝，然后我们进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝，拷贝完成后将创建的新节点的指针返回，即可完成当前节点的两指针的赋值。

具体地，我们用哈希表记录每一个节点对应新节点的创建情况。遍历该链表的过程中，我们检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况。如果这两个节点中的任何一个节点的新节点没有被创建，我们都立刻递归地进行创建。当我们拷贝完成，回溯到当前层时，我们即可完成当前节点的指针赋值。注意一个节点可能被多个其他节点指向，因此我们可能递归地多次尝试拷贝某个节点，为了防止重复拷贝，我们需要首先检查当前节点是否被拷贝过，如果已经拷贝过，我们可以直接从哈希表中取出拷贝后的节点的指针并返回即可。

在实际代码中，我们需要特别判断给定节点为空节点的情况。

实现

方案B、迭代 + 节点拆分​