Part 2 – Introduce Dummy Node in Linked List
Dummy Node技术在链表中是非常非常重要的，它可以避免复杂的分情况讨论，简化思路和代码，还可以提高正确率。切记，当题目要求可能会改变链表头部或者要创建一个新的链表的时候，请务必使用Dummy Node。下面同样选取例题进行讲解该技术，其中前4题是由于需要改变链表头而使用Dummy Node，而后2题是因为需要创建一个新的链表而使用Dummy Node，创建新链表时常和pre指针一同使用。
82. Remove Duplicates from Sorted List II
https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/
由于头部结点可能有重复所以也可能被删掉，此时就需要使用Dummy Node来避免讨论，题目比较简单，理清每种情况的应对方法即可。
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
pre = dummy = ListNode(0)
cur = pre.next = head
while cur and cur.next:
while cur.next and cur.val == cur.next.val:
cur = cur.next
if pre.next == cur:
pre = pre.next
cur = cur.next
else:
pre.next = cur.next
cur = cur.next
return dummy.next
92. Reverse Linked List II
https://leetcode.com/problems/reverse-linked-list-ii/description/
当m = 1时，链表头部也是需要参与反转的，此时Dummy Node又有出场的机会了。同时，注意下m，n与移动次数的关系即可。
代码如下：
class Solution:
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
dummy = pre = ListNode(0)
dummy.next = head
count = m - 1
while count > 0:
pre = pre.next
count -= 1
cur = pre.next
count = n - m
while count > 0:
next = cur.next.next
cur.next.next = pre.next
pre.next = cur.next
cur.next = next
count -= 1
return dummy.next
24. Swap Nodes in Pairs
https://leetcode.com/problems/swap-nodes-in-pairs/description/
由于要改变相邻两个结点的位置，所以会改变头结点的位置，因此需要Dummy Node。这道题相对简单，不再赘述。
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
dummy = pre = ListNode(0)
dummy.next = cur = head
while cur and cur.next:
next = cur.next.next
cur.next.next = pre.next
pre.next = cur.next
cur.next = next
pre = cur
cur = next
return dummy.next
25. Reverse Nodes in k-Group
https://leetcode.com/problems/reverse-nodes-in-k-group/description/
由于这道题也会改变链表的头结点，Dummy Node必不可少。使用一个count变量来记录反转段结点数量是否足够k个。注意reverse方法的写法。
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if not head or not head.next:
return head
dummy = pre = ListNode(0)
dummy.next = cur = head
count = 0
while cur:
count += 1
next = cur.next
if count == k:
pre = self.reverse(pre, next)
count = 0
cur = next
return dummy.next
def reverse(self, pre, next):
cur = pre.next
while cur.next != next:
temp_next = cur.next.next
cur.next.next = pre.next
pre.next = cur.next
cur.next = temp_next
return cur
