LeetCode #82 #92 #24 #25 2018-08

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