查找两个链接列表的合并(相交)点☆☆☆☆

作者 : IT 大叔 本文共1886个字,预计阅读时间需要5分钟 发布时间: 2020-10-13

假设有两个不同长度的列表,它们合并在一个点上;我们如何知道合并点在哪里?

条件:

  1. 我们不知道长度

查找两个链接列表的合并(相交)点☆☆☆☆插图

解:

可以说这违反了“仅分析每个列表一次”的条件,但是实现了乌龟和野兔算法(用于查找循环列表的合并点和循环长度),因此您从列表1开始,并且在到达列表NULL时您假装它是指向列表2开头的指针,从而创建了循环列表的外观。然后,该算法将告诉您确切的合并列表1有多远。

算法步骤:

  • 制作一个如下的指针:
    • 它每次都前进直到结束,然后
    • 跳转到相反列表的开头,依此类推。
  • 创建其中两个,指向两个头。
  • 每次将每个指针前进1,直到它们在交点(IP)处相遇。一两次通过之后,就会发生这种情况。

要了解它,请计算从head1-> tail1 -> head2 -> intersection point和传播的节点数head2 -> tail2-> head1 -> intersection point。两者将相等(绘制链表的diff类型以进行验证)。原因是两个指针head1-> IP + head2->IPIP再次到达之前必须经过相同的距离。因此,到它到达的时间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小站 » 查找两个链接列表的合并(相交)点☆☆☆☆

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论