Linked List Problem

链表中Dummy Node的使用场景

• 需要对链表进行增删改的时候，通常需要用到dummy node，这是为了方便避开空节点问题
• 快慢指针的问题
  • Leetcode 141. 环形链表无需用到dummy node，因为dummy node主要用于简化对linkedlist头部的操作（如需要对头部节点进行修改），而检测环的问题与头部操作关系不大。
  • Leetcode 876. 链表的中间节点也无需用到dummy node。但有一种特殊情况，也就是在偶数链表中，要求返回的是前一个中间节点，则需要用到dummy node来将偶数链表转化为奇数链表。具体可见下面的快慢指针章节。

快慢指针

循环判断条件

通常的写法：

while(fast!=null && fast.next!=null){
  //fast为空说明头节点为空 或者 走到了一个空节点
  //fast.next为空说明现在fast走到了最后一个节点
  //用&&是因为如果fast或者fast.next任何一个为空，都代表算法应该结束
}

中间节点问题

Leetcode 876. 链表的中间节点 中，因为fast指针速度是slow指针的两倍，因此当fast走完时，slow指针应该恰好走到中间节点

• 因为fast每次走两步，而链表的节点个数会影响他走到最后的位置，因此可能出现以下两种情况：

Dummy Node什么时候用？

在第一种情况中，如果我们被要求返回前一个中点（即图中第二个节点），则可以使用虚拟节点来将该偶数链表转化为奇数链表，此时返回的就是图中实际的第二个节点

简单记忆（增加解题速度）

• 奇数个节点的链表，快慢指针得到的就是正中间的节点
• 偶数个节点的链表，快慢指针得到的是后面的中间节点。
  • 若需要得到前面的中间节点，需要使用dummy node。

ps：实在记不住其实简单的想一下画个图也行。