代码随想录算法训练营第五天| 面试题02.07.链表相交、leetcode142 环形链表II

1. leetcode面试题02.07.链表相交

题目链接：面试题 02.07. 链表相交 - 力扣（LeetCode）

文章链接：代码随想录

1.1 代码

跟着老师写的一个版本，自己能理解思路了，但是写的话可能还是有一些难

# 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:
        lenA ,lenB = 0,0
        cur =headA
        while cur:
            cur = cur.next
            lenA +=1
        cur = headB
        while cur:
            cur = cur.next
            lenB +=1
        curA,curB = headA,headB
        if lenB>lenA:
            lenA,lenB = lenB,lenA
            curA,curB = curB,curA
        for _ in range(lenA-lenB):
            curA = curA.next
        while curB:
            if curA == curB:
                return curA
            else:
                curA = curA.next
                curB = curB.next
        return None

1.2 小结

1. 这一块就是判断位置相同，就返回，思路就是我先将两个链表的尾部进行对齐，尾部对齐后的数据就可以进行判断，如果找到了这连个位置的指针处的值相等则返回，否则就继续向后找的一个思路

2 leetcode142 环形链表II

题目链接：142. 环形链表 II - 力扣（LeetCode）

文章链接：代码随想录

视频链接：把环形链表讲清楚！ 如何判断环形链表？如何找到环形链表的入口？ LeetCode：142.环形链表II_哔哩哔哩_bilibili

2.1代码

这道题，怎么说呢，字少但是看了不会，第一次刷这种题，我也放过自己，就是嗯，看看别人怎么做的去学习思路就好了

# 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 = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                index1 = head
                index2 = slow
                while index1!=index2:
                    index1 = index1.next
                    index2 = index2.next
                return index1
        return None

2.2小结

1. 判断链表是不是环形链表就是找两个指针，判断快慢指针会不会相等，因为转圈的时候快的和慢的指针总会相遇
2. 判断两个指针的相遇位置方法就是通过里面推理，最后发现从相遇位置给一个指针和从起始位置给一个指针，两者不断进行走，总会相遇