博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【LeetCode每天一题】 Intersection of Two Linked Lists(两个链表的入口节点)
阅读量:6825 次
发布时间:2019-06-26

本文共 3142 字,大约阅读时间需要 10 分钟。

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 = 3Output: Reference of the node with value = 8Input 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 = 1Output: Reference of the node with value = 2Input 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 = 2Output: nullInput 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. 思路

  这道题意思就是让我们求两个链表第一个公共节点,第一种办法就是暴力破解法,我们先将一个链表的节点都存进辅助列表中。然后遍历第二个链表,每一次都判断是否在辅助列表中,当遍历完毕之后没找到说明不存在入口节点,存在则直接返回。但是这种算法的时间复杂度较高O(m*n),当列表数目过多时,会存在超时的问题。还有一种办法就是如果两个链表存在入口时,入口节点后面的元素数目都是相同的,根据这一个规则我们可以设置设置两个指针分别指向两个链表的头节点,然后开始遍历。当第一个指针指向链表A遍历完毕之后,将其指向链表B的头部。第二个指针指向链表B遍历完毕之后将其指向链表A,然后循环遍历,当两个节点相同时终止遍历,如果存在入口节点则终止时则会指向入口节点,否则指向None。 解决代码

  第一种解决代码
1 # Definition for singly-linked list. 2 # class ListNode(object): 3 #     def __init__(self, x): 4 #         self.val = x 5 #         self.next = None 6  7 class Solution(object): 8     def getIntersectionNode(self, headA, headB): 9         """10         :type head1, head1: ListNode11         :rtype: ListNode12         """     13         if not headA or not headB:14             return None15         tem_list = []16         while headA:         # 先将链表A中的节点进行存储17             tem_list.append(headA)18             headA = headA.next19         while headB:      # 然后遍历链表B进行节点的查找20             if headB in tem_list:21                 return headB22             headB = headB.next23         return None
第二种解决代码
1 # Definition for singly-linked list. 2 # class ListNode(object): 3 #     def __init__(self, x): 4 #         self.val = x 5 #         self.next = None 6  7 class Solution(object): 8     def getIntersectionNode(self, headA, headB): 9         """10         :type head1, head1: ListNode11         :rtype: ListNode12         """     13         pa, pb = headA, headB          # 两个指针指向两个链表14         while pa is not pb:           # pa不等于pb,15             pa = pa.next if pa else headB        # 遍历到尾部时,pa指向headB头部16             pb = pb.next if pb else headA          # 遍历到尾部时,pb指向headA的头部17         return pa

转载于:https://www.cnblogs.com/GoodRnne/p/10989096.html

你可能感兴趣的文章
TCP协议三次握手过程分析
查看>>
set排序(个人模版)
查看>>
Codeforces Round #404 (Div. 2) D. Anton and School - 2 数学
查看>>
windows进程中的几个杂项-hpguard 进程终止
查看>>
Window 7 + Ubuntu 双系统安装
查看>>
instance 怎么获得自己的 Metadata - 每天5分钟玩转 OpenStack(169)
查看>>
以AVL树为例理解二叉树的旋转(Rotate)操作
查看>>
Maven可以提交到官方公共仓库maven.org
查看>>
屏幕适配经验
查看>>
学霸也要会看书
查看>>
解读tensorflow之rnn 的示例 ptb_word_lm.py
查看>>
Linux内核--并发【转】
查看>>
关于对FLASH开发,starling、starling feathers、starling MVC框架的理解
查看>>
【Python】京东商品价格监控
查看>>
Codeforces 10A-Power Consumption Calculation(模拟)
查看>>
Project Euler:Problem 42 Coded triangle numbers
查看>>
李洪强iOS开发之Block和协议
查看>>
Python 调用snmp自定义OID实现监控
查看>>
Spark Streaming概念学习系列之SparkStreaming性能调优
查看>>
hdu 5375 - Gray code(dp) 解题报告
查看>>