1. 原始题目
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
begin to intersect at node c1.
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.
- Notes:
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.
2. 题目理解
就是找两个链表的交叉结点. 注意: 空链表; 不存在交叉点的链表
3. 解题
思路: 用两个栈: 依次将链表 a 和 b 分别进栈. 然后出栈时比较两个元素是否相等. 如果遇到不同的结点, 那么该结点的上一个结点就是交叉节点.
- # 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 headA is None or headB is None: # 空链表处理
- return None
- results = None
- stacka = []
- stackb = []
- a = headA
- b = headB
- while(a): # a 进栈
- stacka.append(a)
- a = a.next
- while(b): # b 进栈
- stackb.append(b)
- b = b.next
- i = -1
- if stacka[i]!=stackb[i]: # 头元素都不相等肯定没有交叉点
- return None
- while (stacka[i]==stackb[i]):
- i = i-1
- if abs(i)>len(stacka) or abs(i)>len(stackb):
- break
- results = stacka[i+1] # 返回上一个结点
- return results
当然我在 Leetcode 里发现了更简洁, 漂亮的解法. 如下:
- # the idea is if you switch head, the possible difference between length would be countered.
- # On the second traversal, they either hit or miss.
- # if they meet, pa or pb would be the node we are looking for,
- # if they didn't meet, they will hit the end at the same iteration, pa == pb == None, return either one of them is the same,None
即遍历到链表尾后就交换头结点继续遍历. 在第二次反转时就会相遇或者错过. 如果相遇那么该结点就是交叉点, 错过就是不存在交叉点.
- class Solution:
- # @param two ListNodes
- # @return the intersected ListNode
- def getIntersectionNode(self, headA, headB):
- if headA is None or headB is None:
- return None
- pa = headA # 2 pointers
- pb = headB
- while pa is not pb:
- # if either pointer hits the end, switch head and continue the second traversal,
- # if not hit the end, just move on to next
- pa = headB if pa is None else pa.next # 走到该链表末尾后下一步走另个链表开头
- pb = headA if pb is None else pb.next
- return pa # only 2 ways to get out of the loop, they meet or the both hit the end=None
来源: http://www.bubuko.com/infodetail-3012451.html