07、链表（下）

思考

如何轻松写出正确的链表代码？比如链表反转、有序链表合并等操作代码

主要内容

理解指针

指针：存储所指对象的内存地址
举例：p -> next = q
意思：p 结点的 next 指针存储了 q 结点的内存地址

指针丢失

什么是指针丢失？指着指着指针的值就不正确了，导致链表结构断裂
举例链表插入操作：在 a、b 之间插入 x，p 指向 a

p.next = x
x.next = p.next // 这行代码导致 x.next 指向了自己，链表断裂，“指针丢失”

边界问题

经常要考虑的边界问题有：

1. 链表为空，代码是否正常运行？
2. 链表只有一个结点，代码是否正常运行？
3. 链表只有两个结点，代码是否正常运行？
4. 链表在处理头和尾巴时，代码是否正常运行？

举例与画图

针对复杂的链表操作，可以通过据实际列子与画图来理清楚思路

多写多练

写链表代码是最考验逻辑思维能力的。
因为，链表代码到处都是指针的操作、边界条件的处理，稍有不慎就容易产生 Bug。
链表代码写得好坏，可以看出一个人写代码是否够细心，考虑问题是否全面，思维是否缜密。
所以，这也是很多面试官喜欢让人手写链表代码的原因。

新的思考

单链表反转

举例：
正序head->[a|next]->[b|next]->[c|next]->[d|next]->null
反转head->[d|next]->[c|next]->[b|next]->[a|next]->null

实现思路：

• 链表只能从头到尾的查找，所以从 head 循环找到每一个
• 链表之间的关联是靠next，所以每次要暂存下next，免得中断了

function reserve(ListNode) {
  if(!ListNode || !ListNode.head) {
    // 空链表
    return ListNode
  }

  if(ListNode.head.next === null) {
    // 只有一个结点的链表
    return ListNode
  }

  let prev = null
  let curr = ListNode.head
  let next = curr.next

  while(curr) {
    curr.next = prev
    prev = curr
    curr = next
    next = curr?.next
  }

  ListNode.head = prve
}

链表中环的检测

检测：链表中是否存在某个节点的下一个节点是链表中前面某个节点的情况。
举例：
有环head->[a|next]->[b|next]->[c|next]->[d|next]->[a|next]
思路：

• 快慢指针法：慢走一格，快走两格，有环则快会追上慢，无环则快指为 null

function isCricle(head) {
  if (!head || !head.next) {
    // 链表为空或只有一个节点时，不可能存在环
    return false;
  }

  let slow = head // 第一个
  let fast = head.next // 第二个

  while(fast !== null && fast.next !== null) {
    if(slow === fast) {
     return true
    }
    fast = fast.next.next
    slow = slow.next
  }

  return false
}

两个有序的链表合并

举例：
链 表1: 1 -> 3 -> 5 -> null
链表2: 2 -> 4 -> 6 -> 7 -> null
合并后的新链表为：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null

function hebing(head1, head2) {
  let curr1 = head1
  let curr2 = head2

  let curr3 = newListNode.head

  while(curr1 && curr2) {
    if(curr1.value <= curr2.value) {
      curr3.next = curr1
      curr1 = curr1.next
    } else {
      curr3.next = curr2
      curr2 = curr2.next
    }
    curr3 = curr3.next; // 移动curr3到下一个节点位置
  }

  if(curr1) curr3.next = curr1.next
  else curr3.next = curr2.next

  return curr3.head
}

删除链表倒数第 n 个结点

举例：
链表: 1 -> 3 -> 5 -> 7 -> null，删除倒数第 2 个后变为 1 -> 3 -> 7 -> null
思路：找到倒数 n + 1，改变它的 next 指向 n - 1

// 获取链表的总长度
function getLen(head) {
  let i = 0

  if(!head) return i

  let next = head.next
  while(next) {
    i++
    next = next.next
  }
  return i
}

// 删除正数第 n 个
function deleteByNum(head, num) {
  let prev = null
  let curr = null
  let next = null

  // 找到正数第 n 个
  for(let i = 0; i < num; i++) {
    prev = curr
    curr = head.next
    next = curr.next
  }

  prev.next = next
}

function delete(head, num){
  const len = getLen(len)
  if(len) deleteByNum(head, len - num)
}

求链表的中间结点

通过快慢两个指针，慢每次跳一个，快每次跳两个，当快走完时，慢刚好就在中间
若链表长度为偶数，则有两个中心点，慢刚好指向[中心点 2]
若链表长度为奇数，则有一个中心点，慢刚好指向[中心点]

function getCenter(head) {
  if(!head && !head.next) return head

  let fast = head
  let slow = head
  let prev = null

  while(fast && fast.next){
    fast = fast.next.next
    prev = slow
    slow = slow.next
  }

  if(fast === null) {
    // 表明 链表长度为偶数，则中心点有两个
    return [prev, slow]
  } else return slow
}