160.环形链表

题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

思路

1.哈希表
判断两个链表是否相交，可以使用哈希集合存储链表节点。
首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中：
如果当前节点不在哈希集合中，则继续遍历下一个节点；
如果当前节点在哈希集合中，则后面的节点都在哈希集合中，即从当前节点开始的所有节点都在两个链表的相交部分，因此在链表 headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点，返回该节点。
如果链表 headB 中的所有节点都不在哈希集合中，则两个链表不相交，返回 null。
2.双指针
只有当链表 headA 和 headB 都不为空时，两个链表才可能相交。因此首先判断链表 headA 和 headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。
当链表 headA 和 headB 都不为空时，创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：
每步操作需要同时更新指针 pA 和 pB。
如果指针 pA 不为空，则将指针 pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点。
如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点。
当指针 pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。

代码

# 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
        """
        if not headA or not headB:
            return None
        seen = set()
        p1 = headA
        p2 = headB
        while p1 is not None:
            seen.add(p1)
            p1 = p1.next

        while p2 is not None:
            if p2 in seen:
                return p2.val
            p2 = p2.next

        return None

    def getIntersectionNode1(self, headA, headB):
        """
        双指针

        :param headA:
        :param headB:
        :return:
        """
        if not headA or not headB:
            return None

        p_A = headA
        p_B = headB

        while p_A != p_B:
            p_A = headB if p_A is None else p_A.next
            p_B = headA if p_B is None else p_B.next

        return p_A


    def create_linked_list(self):
        """
        创建两个相交的单链表
        :return:两个相交但表表的头指针
        """
        a_node1 = ListNode(4)
        a_node2 = ListNode(1)

        b_node1 = ListNode(5)
        b_node2 = ListNode(0)
        b_node3 = ListNode(1)

        common_node1 = ListNode(8)
        common_node2 = ListNode(4)
        common_node3 = ListNode(5)

        a_node1.next = a_node2
        a_node2.next = common_node1
        common_node1.next = common_node2
        common_node2.next = common_node3

        b_node1.next = b_node2
        b_node2.next = b_node3
        b_node3.next = common_node1
        common_node1.next = common_node2
        common_node2.next = common_node3

        return a_node1, b_node2


if __name__ =="__main__":
    slt = Solution()

    head_a, head_b = slt.create_linked_list()

    intersected_node = slt.getIntersectionNode1(head_a, head_b)
    print(intersected_node.val)

victory的博客

leetcode | 160.相交链表

160.环形链表

题目描述

思路

代码