# 代码随想录算法训练营第四天 | 24. Swap Nodes in Pairs、160. Intersection of Two Linked Lists、19. Remove Nth Node From End of List、142. Linked List Cycle II

## 24. Swap Nodes in Pairs


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        cur = dummy

        while cur.next and cur.next.next:
            tmp = cur.next
            tmp1 = cur.next.next.next

            cur.next = cur.next.next
            cur.next.next = tmp
            tmp.next = tmp1

            cur = cur.next.next
        return dummy.next

## 160. Intersection of Two Linked Lists

兩個linkedlist有沒有交叉點，如果有返回那個點，沒有就返回None

# 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) -> Optional[ListNode]:
        l1, l2 = headA, headB
        while l1 != l2:
            l1 = l1.next if l1 else headB
            l2 = l2.next if l2 else headA
        return l1

## 19. Remove Nth Node From End of List
為了刪除方便 需要找到第n-1個node才能刪除 倒數第n個node
怎麼找？
快慢指針！ 快指針先走n+1步
快慢指針同時前進 慢指針就會落在n-1
慢指針再把下一個指針伸到下下一個就可以了
T:O(n)
S:O(1)

# 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: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        slow, fast = dummy, dummy

        for i in range(n+1):
            fast = fast.next
        
        while fast:
            fast = fast.next
            slow = slow.next
        
        slow.next = slow.next.next
        return dummy.next

## 142. Linked List Cycle II

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

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        return None