# 链表

链表的类型
1. 合并
2. 删除
3. 反转双指针
4. 成环快慢指针
5. 多个链表归并

# 问题

为什么需要 dummy 节点

作为头结点
解决头部极端情况

当你需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。

// 移动指针
const cur = head // 当前指针

cur = cur.next

// 删除cur结点 需要找到前一个指针
const pre.next = cur // 找到前指针
pre.next = pre.next.next

// 插入结点
const pre.next = cur // 找到前指针

const newNode = new ListNode() // 插入的指针

cur.next = pre.next
pre.next = cur

// 交换两个结点
const next = cur.next
cur.next = per

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

# 链表的基本操作-遍历

function listFor(l1) {
  let current = l1 // 链表要循环 先要有一个游标 来定位当前的结点位置
  while (current) {
    cur = cur.next // 游标的移动
  }
}

listFor(l1)

TIP

遍历需要用到一个指针 current = current.next

# 链表的重复删除

83. 删除排序链表中的重复元素 (opens new window)

真题描述：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。输入: 1->1->2 输出: 1->2

var deleteDuplicates = function (head) {
  // 因为是已经排序了 所以相同的元素就在右边
  // 定义一个指针用来维持链表的移动
  let current = head
  // 遍历链表
  while (current && current.next) {
    // 如果当前值和下一个元素相等 就删除下一个元素 否则指针移动
    if (current.val === current.next.val) {
      // 删除
      current.next = current.next.next
    } else {
      // 相等的时候不移动是因为这个值可能还和下一个值相等
      current = current.next
    }
  }
  return head
}

TIP

删除结点的步骤

current.next = current.next.next
删除之后不在移动游标

# 链表的合并

21. 合并两个有序链表 (opens new window)

真题描述：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

TIP

处理链表的本质，是处理链表结点之间的指针关系。

var mergeTwoLists = function (list1, list2) {
  // 返回的是一个新的链表
  const head = new ListNode(-1)
  let current = head
  // 遍历list1 和list2 链表遍历要靠指针
  let p1 = list1
  let p2 = list2

  while (p1 && p2) {
    if (p1.val > p2.val) {
      // p2 更小
      current.next = p2
      p2 = p2.next
    } else {
      // p1 更小
      current.next = p1
      p1 = p1.next
    }
    current = current.next
  }
  if (p1) {
    current.next = p1
  }

  if (p2) {
    current.next = p2
  }

  return head.next
}

TIP

链表的添加节点 cur.next = next

# 删除问题的延伸

82. 删除排序链表中的重复元素 II (opens new window)

真题描述：给定一个排序链表，删除所有含有重复数字的结点，只保留原始链表中没有重复出现的数字。

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

function deleteMutNumber(list) {
  if (list === null || list.next === null) {
    return
  }
  const dummy = new ListNode()

  dummy.next = list

  let cur = dummy

  // 链表的循环退出结点的判断  怎么证明结点有没有值 上一个结点的next 为null
  while (cur.next && cur.next.next) {
    if (cur.next.val === cur.next.next.val) {
      cur.next = cur.next.next
      let val = cur.next.val
      // 反复地排查后面的元素是否存在多次重复该值的情况
      while (cur.next && cur.next.val === val) {
        // 若有，则删除   链表的删除 怎么删除一个结点   这个结点的上一个结点直接指向这个结点的下一个结点
        cur.next = cur.next.next
      }
    } else {
      cur = cur.next // 链表的循环   游标怎么下一步 直接时当前游标重新赋值为一下个结点
    }
  }
  return dummy.next
}

TIP

定义 dummy 节点: const dummy = new ListNode();dummy.next = head

# 快慢指针——删除链表的倒数第 N 个结点

19. 删除链表的倒数第 N 个结点 (opens new window)

真题描述：给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个结点后，链表变为 1->2->3->5.

var removeNthFromEnd = function (head, n) {
  const dum = new ListNode()
  dum.next = head
  let fast = dum
  let slow = dum
  for (let i = 0; i < n; i++) {
    fast = fast.next
  }

  while (fast.next !== null) {
    slow = slow.next
    fast = fast.next
  }

  slow.next = slow.next.next
  return dum.next
}

# 多指针法——链表的反转

206. 反转链表 (opens new window)

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

function (head){
  let per = null
  let cur  = head
  while(cur!==null){
    const next = cur.next
    cur.next = per
    per = cur
    cur = next
  }
  return per
}

TIP

反转就是找到前驱结点和当前结点

反转一个结点的链接
移动前驱和当前结点

# 局部反转一个链表

反转链表 II (opens new window)

真题描述：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

var reverseBetween = function (head, left, right) {
  // 定义pre、cur，用leftHead来承接整个区间的前驱结点
  let pre, cur, leftHead

  const dumany = new ListNode()

  dumany.next = head
  // 游标
  let p = dumany

  for (let i = 0; i < left - 1; i++) {
    p = p.next
  }

  leftHead = p

  let start = p.next

  per = start

  cur = start.next

  for (let i = 0; i < right - left; i++) {
    const next = cur.next
    cur.next = per
    per = cur
    cur = next
  }

  leftHead.next = per
  // 将区间内反转后的最后一个结点 next 指向 cur
  start.next = cur

  return dumany.next
}

TIP

局部反转先找到开始反转节点的前驱节点

TIP

链表做题前画图

# 环形链表基本问题——如何判断链表是否成环

141. 环形链表 (opens new window)

真题描述：给定一个链表，判断链表中是否有环。输入：[3,2,0,4] pos=1 输出：true

// 立flag
var hasCycle = function (head) {
  while (head) {
    if (head.flag) {
      return true
    } else {
      head.flag = true
      head = head.next
    }
  }
  return false
}

// 双指针

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

147. 对链表进行插入排序 (opens new window)

148. 排序链表 (opens new window)

var insertionSortList = function (head) {
  const dummy = new ListNode()
  dummy.next = head

  // 定义一前一后两个结点 如果右边的比左边的大就执行删除 查找 插入操作
  let lastP = head
  let current = head.next

  while (current) {
    if (lastP.val <= current.val) {
      lastP = lastP.next
      current = lastP.next
    } else {
      //  查找第一个比current大的结点
      let pre = dummy
      while (pre.next && pre.next.val <= current.val) {
        pre = pre.next
      }
      // 删除链接
      lastP.next = current.next

      // 插入前面

      current.next = pre.next
      pre.next = current

      // 移动指针
      current = lastP.next
    }
  }
  return dummy.next
}

86. 分隔链表 (opens new window)

var partition = function (head, x) {
  const smallDummy = new ListNode()
  const largeDummy = new ListNode()
  let smallP = smallDummy
  let largeP = largeDummy
  while (head) {
    if (head.val < x) {
      smallP.next = head
      smallP = smallP.next
    } else {
      largeP.next = head
      largeP = largeP.next
    }
    head = head.next
  }
  largeP.next = null
  smallP.next = largeDummy.next

  return smallDummy.next
}

反转链表 →