LeetCode #141 #142 #160 2018-08-

Part 3 – Two Pointers

Two Pointers技术，也被称为Walker & Runner技术，是解决很多链表题目的利器。用法分为两种：第一种，walker每次移动一步而runner每次移动两步，一般用来解决Linked List Cycle这类找循环点的题目；第二种，walker和runner速度一样，一般用来解决Remove Nth Node From End of List这类要找倒数第几个结点或者要求walker和runner之间有固定距离的题目。下面同样选取例题进行讲解该技术，其中前3题是由于需要寻找循环点而使用Two Pointers技术，而后2题是因为需要找到特定点而使用Two Pointers技术。请仔细体会Two Pointers技术的用法。

141. Linked List Cycle

https://leetcode.com/problems/linked-list-cycle/description/

最经典的walker & runner技术用法，walker每次移动1步，runner每次移动2步，如果有循环walker和runner终会在某个结点相遇。
代码如下：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return False
        walker = head
        runner = head
        while runner and runner.next:
            walker = walker.next
            runner = runner.next.next
            if walker == runner:
                return True
        return False

142. Linked List Cycle II

https://leetcode.com/problems/linked-list-cycle-ii/description/

该题是上道题的升级版，在确认是否有循环的同时，如果有还要找到循环的起始点。由k = a + b + mc和2k = a + b + nc可得k = (n - m)c = a + b + mc可得a = (n – 2m)c – b。可知从链表头和相交点到循环点的距离是相同的。
代码如下：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return None
        walker = runner = head
        while runner and runner.next:
            walker = walker.next
            runner = runner.next.next
            if walker == runner:
                break
        if walker != runner:
            return None
        walker = head
        while walker != runner:
            walker = walker.next
            runner = runner.next
        return walker

160. Intersection of Two Linked Lists

https://leetcode.com/problems/intersection-of-two-linked-lists/description/

这道题有3种解法，其中第三种使用了Two Pointers技术，原理和上一道题一样，但并不推荐，因为要改变链表结构再改回来，推荐前2种解法。

第一种思想很简单，先找出两个链表的长度len1, len2，让长的链表先走abs(len1 - len2)步，然后两个链表同时往前走直到交点。
代码如下：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        walker = headA
        runner = headB
        lengthA = 1
        lengthB = 1
        while walker:
            walker = walker.next
            lengthA += 1
        while runner:
            runner = runner.next
            lengthB += 1
        if lengthA < lengthB:
            headA, headB = headB, headA
            lengthA, lengthB = lengthB, lengthA
        count = lengthA - lengthB
        while count:
            headA = headA.next
            count -= 1
        while headA != headB:
            headA = headA.next
            headB = headB.next
        return headA

第二种思想很巧妙，当一个链表走完时，切换到另一个链表接着走，直到交点。
代码如下：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        walker = headA
        runner = headB
        while walker and runner:
            walker = walker.next
            runner = runner.next
        if not walker:
            walker = headB
            while runner:
                walker = walker.next
                runner = runner.next
            runner = headA
        else:
            runner = headA
            while walker:
                walker = walker.next
                runner = runner.next
            walker = headB
        while walker != runner:
            walker = walker.next
            runner = runner.next
        return walker

第三种，把b1，c3结点链接起来，即可转换为上一道题。