合并两个链表

1669. 合并两个链表

给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。

请你将 list1 中下标从 a 到 b 的全部节点都删除，并将 list2 接在被删除节点的位置。

示例 1:

输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出：[0,1,2,1000000,1000001,1000002,5]
解释：我们删除 list1 中下标为 3 和 4 的两个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。

示例 2:

输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]
解释：上图中蓝色的边和节点为答案链表。

代码

const list1 = {
  'val':1,
  'next':{
    'val':2,
    'next':{
      'val':3,
      'next':{
        'val':4,
        'next':{
          'val':5,
          'next':undefined
        }
      }
    }
  }
}

const list2 = {
  'val':'a',
  'next':{
    'val':'b',
    'next':{
      'val':'c',
      'next':undefined
    }
  }
}

const a = 3
const b = 4

思路：第一部分、第二部分（删除并插入新节点）、第三部分

声明 ListNode 节点函数
因为头节点有可能发生变化：使用虚拟头节点可以避免复杂的分类讨论
声明头尾节点 fast/last 和 count = -1 计数
获取 fast 节点和 last 节点（通过计数器）
获取新链表尾节点
连接新链表

// 1. 声明 ListNode 节点函数
class ListNode {
  constructor(val, next) {
    this.val = val || 0
    this.next = next || null
  }
}

var mergeInBetween = function (list1, a, b, list2) {
  // 2. 因为头节点有可能发生变化：使用虚拟头节点可以避免复杂的分类讨论
  let dummyNode = new ListNode(-1, list1)
  let current = dummyNode

  // 3. 声明头尾节点 `fast/last` 和 `count = -1` 计数
  let first = (last = null)
  let count = -1 // 计数器 ：等价于for中i

  // 4. 获取 fast 节点和 last 节点（通过计数器）
  while (current) {
    count++
    if (count == a) {
      first = current
    }
    if (count == b) {
      last = current.next.next // !测试出
    }
    current = current.next
  }

  // 5. 获取新链表尾节点
  let second = list2
  while (second && second.next) {
    second = second.next
  }

  // 6. 连接新链表
  first.next = list2
  second.next = last

  return dummyNode.next
}

console.log(mergeInBetween(list1, a, b, list2))

1669. 合并两个链表​

代码​

1669. 合并两个链表

代码