查找两个链接列表的合并(相交)点☆☆☆☆
假设有两个不同长度的列表,它们合并在一个点上;我们如何知道合并点在哪里?
条件:
- 我们不知道长度
解:
可以说这违反了“仅分析每个列表一次”的条件,但是实现了乌龟和野兔算法(用于查找循环列表的合并点和循环长度),因此您从列表1开始,并且在到达列表NULL时您假装它是指向列表2开头的指针,从而创建了循环列表的外观。然后,该算法将告诉您确切的合并列表1有多远。
算法步骤:
- 制作一个如下的指针:
- 它每次都前进直到结束,然后
- 跳转到相反列表的开头,依此类推。
- 创建其中两个,指向两个头。
- 每次将每个指针前进1,直到它们在交点(
IP
)处相遇。一两次通过之后,就会发生这种情况。
要了解它,请计算从head1-> tail1 -> head2 -> intersection point
和传播的节点数head2 -> tail2-> head1 -> intersection point
。两者将相等(绘制链表的diff类型以进行验证)。原因是两个指针head1-> IP + head2->IP
在IP
再次到达之前必须经过相同的距离。因此,到它到达的时间IP
,两个指针将相等,并且我们有了合并点。
实现方式:
CS
int FindMergeNode(Node headA, Node headB) {
Node currentA = headA;
Node currentB = headB;
//Do till the two nodes are the same
while(currentA != currentB){
//If you reached the end of one list start at the beginning of the other one
//currentA
if(currentA.next == null){
currentA = headB;
}else{
currentA = currentA.next;
}
//currentB
if(currentB.next == null){
currentB = headA;
}else{
currentB = currentB.next;
}
}
return currentB.data;
}
java
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//boundary check
if(headA == null || headB == null) return null;
ListNode a = headA;
ListNode b = headB;
//if a & b have different len, then we will stop the loop after second iteration
while( a != b){
//for the end of first iteration, we just reset the pointer to the head of another linkedlist
a = a == null? headB : a.next;
b = b == null? headA : b.next;
}
return a;
}
Y
# 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
免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 查找两个链接列表的合并(相交)点☆☆☆☆
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 查找两个链接列表的合并(相交)点☆☆☆☆
常见问题FAQ
- 没有金币/金币不足 怎么办?
- 本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
- 所有资源普通会员都能下载吗?
- 本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。