本文主要是介绍[LeetCode] 160. Intersection of Two Linked Lists，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目内容
https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
Example 1:Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.Example 2:Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.Example 3:Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.题目思路
这道题有一个很巧妙的方法。以例题中为例，我们可以让一个指针在第一个链表中走到尾部，然后再从第二个链表的头部开始继续走。如果他们有相同的部分，那么在走到对方链表的地方时就一定能够交汇。因为他们都走了等同的距离。比如[4,1,8,4,5]
[5,0,1,8,4,5]，他们在交汇前分别走了[4,1,8,4,5,null,50]和[5,0,1,8,4,5,null,4]
程序代码
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution(object):def getIntersectionNode(self, headA, headB):""":type head1, head1: ListNode:rtype: ListNode"""if not headA or not headB:return Nonepa,pb=headA,headBwhile pa!=pb:if pa:pa=pa.nextelse:pa=headBif pb:pb=pb.nextelse:pb=headAreturn pa
这篇关于[LeetCode] 160. Intersection of Two Linked Lists的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
