Two Pointer Technique

本文蒐集

• LeetCode 141
• LeetCode 142
• LeetCode 160
• LeetCode 19

LeetCode 141: Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false

Example:

Constraints:

• The number of the nodes in the list is in the range [0, \(10^4\)].
• \(-10^5\) <= Node.val <= \(10^5\)
• pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

我的解答

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

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        a = head
        b = head
        if head is None:
            return False
        while a.next is not None and a.next.next is not None:
            if a.next is b:
                return True
            a = a.next.next
            b = b.next
        
        return False

LeetCode 142: Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Notice that you should not modify the linked list.

Example:

Constraints:

• The number of the nodes in the list is in the range [0, \(10^4\)].
• \(-10^5\) <= Node.val <= \(10^5\)
• pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

我的解答

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

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if head is None:
            return
        
        first = head
        second = head
        flag = 0
        
        while first.next is not None and first.next.next is not None:
            if first.next is second:
                flag = 1
                # 和上一題差別在於要讓兩個指標碰到
                first = first.next
                break
            
            first = first.next.next
            second = second.next
            
#         網友解
#         if flag == 1:
#             second = second.next
#             while head is not second:
#                 head = head.next
#                 second = second.next
            
#             return head
#         else:
#             return
            m = 0
            first = first.next
            curr2 = head
            # 下面迴圈不會算到指標當下指的node
            while curr2 is not second:
                curr2 = curr2.next
                m += 1
            
            while first is not second:
                count = 0
                curr = head
                
                while curr is not first:
                    curr = curr.next
                    count += 1
                    
                if count < m:
                    m = count
                    
                first = first.next
            
            result = head
            for i in range(m):
                result = result.next
            return result
        else:
            return

LeetCode 160: Intersection of Two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

It is guaranteed that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Example:

Constraints:

• The number of nodes of listA is in the m.
• The number of nodes of listB is in the n.
• 0 <= m, n <= 3 * \(10^4\)
• 1 <= Node.val <= \(10^5\)
• 0 <= skipA <= m
• 0 <= skipB <= n
• intersectVal is 0 if listA and listB do not intersect.
• intersectVal == listA[skipA + 1] == listB[skipB + 1] if listA and listB intersect.

Follow up: Could you write a solution that runs in O(n) time and use only O(1) memory?

我的解答

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        B = headB
        while headB:
            headB.val = -headB.val
            headB = headB.next
        while headA:
            if headA.val < 0:
                break
            headA = headA.next
        else:
            while B:
                B.val = -B.val
                B = B.next
            return
        while B:
            B.val = -B.val
            B = B.next
        return headA

LeetCode 19: Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example:

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Follow up: Could you do this in one pass? ## 我的解答

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        sz = 0
        a = head
        
        while a:
            a = a.next
            sz += 1
        
        if sz == n:
            return head.next
        else:
            a = head
            for i in range(sz-n-1):
                a = a.next
            a.next = a.next.next
            return head