精华内容
下载资源
问答
  • 如何判断两个链表是否有交点
    2018-09-27 15:59:26

    如何判断两个链表是否有交点

    首先,两个链表如果有交点它应该是y型的。

    1. 分别遍历两个链表,如果尾节点地址相同,则有交点
    2. 分别遍历两个链表,计算两链表长度,长的为A,短的为B,让长的链表先走A-B步,然后两个链表仪器走,走到同一地址处为交点。
    3. 把两个链表压到两个栈里,分别将栈顶弹出,比较,知道弹出的地址不同,则上一个弹出的为交点。
    4. 把两个链表放到两个数组中遍历,地址相同为交点。

     

    1. 如何判断单向链表是否有环
    1. 遍历放到链表中,直到重复点出现,即为入口点。
    2. 2个指针,一个一次走一步,一个一次走两步,相遇则有环,从相遇点断开,变为Y型,入口点即为相交点。
    3. 计算环的长度,两个指针p1和p2,p1先走x步,然后两个指针一起走,相遇点为入口点。
    更多相关内容
  • 原地址 ...如图所示,由于a+c+b=b+c+a,所以两个指针在第二次遍历的时候,一定会在相交节点处相遇。 如果没有交点,则第二次遍历结束都是null,遍历结束,返回null a+b=b+a,最终一定都会指向null。 ..

    原地址

    解题思路
    定义双指针,分别指向A和B的头部。

    如果链表一样长且有交点,则第一次遍历就能找到相同交点,返回

    image.png

     

    如果不一样长且有交点,则指针遍历一条链表后,遍历另一条链表
    如:A链表的指针遍历完A了,下一步继续遍历B链表。B链表的指针遍历完B了,下一步继续遍历A链表。

    image.png

     

    如图所示,由于a+c+b=b+c+a,所以两个指针在第二次遍历的时候,一定会在相交节点处相遇。

    如果没有交点,则第二次遍历结束都是null,遍历结束,返回null
    a+b=b+a,最终一定都会指向null。

    其实这种情况也可以这么理解:A和B的相交节点为null,遍历两次,一定能找到相交节点。

    image.png

     

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    
    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            ListNode* a = headA;
            ListNode* b = headB;
            while (a != b)
            {
                a = a != nullptr ? a->next : headB;
                b = b != nullptr ? b->next : headA;
            }
            return a;
        }
    };

    展开全文
  • 设置两个指针一个快指针(每次走两步)一个慢指针(每次走一步),1:两个链表都无环,循环判断交点,2:一个链表环一个无环不可能相交。3:两个链表环(1)两个独立的环不相交,(2)相交但相交的位置在环...

    问题:

    给定两哥可能有环也可能无环的单链表,头节点head1和head2。实现一个函数,如果两个链表相交返回相交的第一个节点,否则返回null。

    要求:
    如果两个链表之和长度为n,时间复杂度请达到O(n).

    解题:
    设置两个指针一个快指针(每次走两步)一个慢指针(每次走一步),1:两个链表都无环,循环判断交点,2:一个链表有环一个无环不可能相交。3:两个链表都有环(1)两个独立的环不相交,(2)相交但相交的位置在环以外,(3)两个链表入环的节点是一个,(4)两个链表入环的节点不是一个。

    代码:

    package class08;
    
    public class Code01_FindFirstIntersectNode {
    	public static class Node{
    		public int val;
    		public Node next;
    		public  Node() {
    			
    		}
    		public Node(int data) {
    			this.val = data;
    		}
    	}
    	public static Node getIntersectNode(Node head1,Node head2) {
    		if(head1==null||head2==null) return null;
    		Node loop1 = getloopNode(head1);
    		Node loop2 = getloopNode(head2);
    		if(loop1==null&&loop2==null) return noloop(head1,head2);
    		else if(loop1!=null&&loop2!=null) {
    			return haveloop(head1,loop1,head2,loop2);
    		}
    		return null;
    	}
    	
    	private static Node haveloop(Node head1, Node loop1, Node head2, Node loop2) {
    		Node cur1 = null;
    		Node cur2 = null;
    		if(loop1 == loop2) {
    			int n = 0;
    			cur1 = head1;
    			cur2 = head2;
    			while(cur1.next!=null) {
    				n++;
    				cur1 = cur1.next;
    			}
    			while(cur2.next!=null) {
    				n--;
    				cur2 = cur2.next;
    			}
    			Math.abs(n);
    			while(n!=0) {
    				cur1 = cur1.next;
    			}
    			while(cur1!=cur2) {
    				cur1 = cur1.next;
    				cur2 = cur2.next;
    			}
    			return cur1;
    		}
    		else {
    			cur1 = loop1.next;
    			while(cur1!=loop1) {
    				if(cur1 == loop2) return loop1;
    				cur1 = cur1.next;
    			}
    		}
    		return null;
    	}
    
    	private static Node noloop(Node head1, Node head2) {
    		Node cur1 = head1;
    		Node cur2 = head2;
    		int n =0;
    		while(cur1.next!=null) {
    			n++;
    			cur1 = cur1.next;
    		}
    		while(cur2.next!=null) {
    			n--;
    			cur2 = cur2.next;
    		}
    		if(cur1!=cur2) return null;
    		cur1 = n>0?head1:head2;
    		cur2 = cur1 == head1?head2:head1;
    		while(n!=0) {
    			n--;
    			cur1 = cur1.next;
    		}
    		while(cur1!=cur2) {
    			cur1 = cur1.next;
    			cur2 = cur2.next;
    		}
    		return cur1;
    	}
    
    	public static Node getloopNode(Node loop) {
    		if(loop==null||loop.next==null||loop.next.next==null) return null;
    		Node fast = loop.next.next;
    		Node slow = loop.next;
    		while(slow!=fast) {
    			if(fast.next==null||fast.next.next==null) return null;
    			slow = slow.next;
    			fast = fast.next.next;
    		}
    		fast = loop;
    		while(slow!=fast) {
    			slow = slow.next;
    			fast = fast.next;
    		}
    		return slow;
    	}
    	public static void main(String[] args) {
    		// 1->2->3->4->5->6->7->null
    		Node head1 = new Node(1);
    		head1.next = new Node(2);
    		head1.next.next = new Node(3);
    		head1.next.next.next = new Node(4);
    		head1.next.next.next.next = new Node(5);
    		head1.next.next.next.next.next = new Node(6);
    		head1.next.next.next.next.next.next = new Node(7);
    
    		// 0->9->8->6->7->null
    		Node head2 = new Node(0);
    		head2.next = new Node(9);
    		head2.next.next = new Node(8);
    		head2.next.next.next = head1.next.next.next.next.next; // 8->6
    		System.out.println(getIntersectNode(head1, head2).val);
    
    		// 1->2->3->4->5->6->7->4...
    		head1 = new Node(1);
    		head1.next = new Node(2);
    		head1.next.next = new Node(3);
    		head1.next.next.next = new Node(4);
    		head1.next.next.next.next = new Node(5);
    		head1.next.next.next.next.next = new Node(6);
    		head1.next.next.next.next.next.next = new Node(7);
    		head1.next.next.next.next.next.next = head1.next.next.next; // 7->4
    
    		// 0->9->8->2...
    		head2 = new Node(0);
    		head2.next = new Node(9);
    		head2.next.next = new Node(8);
    		head2.next.next.next = head1.next; // 8->2
    		System.out.println(getIntersectNode(head1, head2).val);
    
    		// 0->9->8->6->4->5->6..
    		head2 = new Node(0);
    		head2.next = new Node(9);
    		head2.next.next = new Node(8);
    		head2.next.next.next = head1.next.next.next.next.next; // 8->6
    		System.out.println(getIntersectNode(head1, head2).val);		
    
    	}
    
    }
    
    
    展开全文
  • 链表的分类 链表主要分为三类: 单向链表只能从表头到表尾的顺序,每个节点中保存了指向下一...判断两个链表是否相交并找出交点 问题描述: 一个比较经典的问题,判断两个链表是否相交,如果相交找出他们的交点。 解...

    链表的分类

    链表主要分为三类:
    单向链表只能从表头到表尾的顺序,每个节点中保存了指向下一个节点的指针;
    双向链表则可以反向遍历,因为节点中既保存了向后节点的指针,又保存了向前节点的指针。
    循环链表指的是在单向链表和双向链表的基础上,将两种链表的最后一个结点指向第一个结点从而实现循环。

    判断两个链表是否相交并找出交点

    问题描述:

    一个比较经典的问题,判断两个链表是否相交,如果相交找出他们的交点。

    解决方法:

    判断两个链表是否相交并找出交点主要分两种情况

    两个链表均不含有环
    		1.直接法:第一个链表节点是否在两个中
    		2.hash计数法:链表A的节点地址进行hash排序,建立hash表,判断另一节点地址是否在hash表中
    		3.转换链表,查看是否又环
    链表中有环时
    		1.切断链表中的环,判断第二个链表是否又环
    		2.直接判断:一个链表有环,一个链表无环,一定没交点
    
    情况一:两个链表均不含有环

    1、直接法

    采用暴力的方法,遍历两个链表,判断第一个链表的每个结点是否在第二个链表中,**时间复杂度为O(len1len2),耗时很大。

    2、hash计数法

    如 果 两个链表相交,则两个链表就会有共同的结点;而结点地址又是结点唯一标识。因而判断两个链表中是否存在地址一致的节点,就可以知道是否相交了。可以对第一 个链表的节点地址进行hash排序,建立hash表,然后针对第二个链表的每个节点的地址查询hash表,如果它在hash表中出现,则说明两个链表有共 同的结点。
    这个方法的时间复杂度为:O(max(len1+len2);但同时还得增加O(len1)的存储空间存储哈希表。这样减少了时间复杂度,增加 了存储空间

    3.转换链表,查看是否又环
    第三种思路是比较奇特的。先遍历第一个链表到他的尾部,然后将尾部的next指针指向第二个链表(尾部指针的next本来指向的是null)。这样两个链表就合成了一个链表,判断原来的两个链表是否相交也就转变成了判断新的链表是否有环的问题了:即判断单链表是否有环

    情况二:链表中有环时

    1.切断链表中的环,判断第二个链表是否又环

    当两个链表中有环时,相交的判断:
    如果链表有环且相交,那么这两个链表都是有环的。

    找到第一个链表的环点,然后将环断开(当然不要忘记了保存它的下一个节点),然后再来遍历第二个链表,如果发现第二个链表从有环变成了无环,那么他们就是相交的嘛,否则就是不相交的了。

    2.直接判断:一个链表有环,一个链表无环,一定没交点
    当一个链表中有环,一个链表中没有环时,两个链表必不相交。

    其他详细博客

    判断一个链表是否有环

    在这里插入图片描述
    有一个单向链表,链表当中有可能出现“环”,就像题图这样。如何用程序判断出这个链表是有环链表?

    不允许修改链表结构。
    时间复杂度O(n),空间复杂度O(1)。
    
    方法一、穷举遍历

    方法一:首先从头节点开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就从头节点重新遍历新节点之前的所有节点,用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID,则说明该节点被遍历过两次,链表有环;如果之前的所有节点当中不存在相同的节点,就继续遍历下一个新节点,继续重复刚才的操作。

    例如这样的链表:A->B->C->D->B->C->D, 当遍历到节点D的时候,我们需要比较的是之前的节点A、B、C,不存在相同节点。这时候要遍历的下一个新节点是B,B之前的节点A、B、C、D中恰好也存在B,因此B出现了两次,判断出链表有环。

    假设从链表头节点到入环点的距离是D,链表的环长是S。那么算法的时间复杂度是0+1+2+3+….+(D+S-1) = (D+S-1)*(D+S)/2 , 可以简单地理解成 O(N * N)。而此算法没有创建额外存储空间,空间复杂度可以简单地理解成为O(1)。

    方法二、哈希表缓存

    首先创建一个以节点ID为键的HashSet集合,用来存储曾经遍历过的节点。然后同样是从头节点开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就用新节点和HashSet集合当中存储的节点作比较,如果发现HashSet当中存在相同节点ID,则说明链表有环,如果HashSet当中不存在相同的节点ID,就把这个新节点ID存入HashSet,之后进入下一节点,继续重复刚才的操作。

    这个方法在流程上和方法一类似,本质的区别是使用了HashSet作为额外的缓存。

    假设从链表头节点到入环点的距离是D,链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1), 所以总体的时间复杂度是1*(D+S)=D+S,可以简单理解为O(N)。而算法的空间复杂度还是D+S-1,可以简单地理解成O(N)。

    方法三、快慢指针

    首先创建两个指针1和2(在java里就是两个对象引用),同时指向这个链表的头节点。然后开始一个大循环,在循环体中,让指针1每次向下移动一个节点,让指针2每次向下移动两个节点,然后比较两个指针指向的节点是否相同。如果相同,则判断出链表有环,如果不同,则继续下一次循环。

    例如链表A->B->C->D->B->C->D,两个指针最初都指向节点A,进入第一轮循环,指针1移动到了节点B,指针2移动到了C。第二轮循环,指针1移动到了节点C,指针2移动到了节点B。第三轮循环,指针1移动到了节点D,指针2移动到了节点D,此时两指针指向同一节点,判断出链表有环。

    此方法也可以用一个更生动的例子来形容:在一个环形跑道上,两个运动员在同一地点起跑,一个运动员速度快,一个运动员速度慢。当两人跑了一段时间,速度快的运动员必然会从速度慢的运动员身后再次追上并超过,原因很简单,因为跑道是环形的。

    /**
     * 判断单链表是否存在环
     * @param head
     * @return
     */
    public static <T> boolean isLoopList(ListNode<T> head){
        ListNode<T> slowPointer, fastPointer;
    
        //使用快慢指针,慢指针每次向前一步,快指针每次两步
        slowPointer = fastPointer = head;
        while(fastPointer != null && fastPointer.next != null){
            slowPointer = slowPointer.next;
            fastPointer = fastPointer.next.next;
    
            //两指针相遇则有环
            if(slowPointer == fastPointer){
                return true;
            }
        }
        return false;
    }
    

    假设从链表头节点到入环点的距离是D,链表的环长是S。那么循环会进行S次(为什么是S次,有心的同学可以自己揣摩下),可以简单理解为O(N)。除了两个指针以外,没有使用任何额外存储空间,所以空间复杂度是O(1)

    展开全文
  • 解题思路 情况1:两个链表均不含有环 ...可以对第一 个链表的节点地址进行hash排序,建立hash,然后针对第二个链表的每个节点的地址查询hash,如果它在hash中出现,则说明两个链表有共 同的结点。这个方法
  • 原文;... 题目:给两个单链表,如何判断两个单链表是否相交?若相交,则找出第一个相交的节点。...因为两个链表一个共同节点,则这个节点里的指针域指向的下一个节点地址一样,所以下一个节点也会相交,依次
  • 判断两个可能有环的链表是否有交点两个单链表相交的一系列问题首先需要判断单链表是否有环hashSet(很简单,不多说,空间复杂度O(n))快慢指针接下来就需要解决有无交点的问题:两个无环链表是否有交点两个有环链...
  • 判断两个链表是否相交,如果两个链表相交,两个链表有相同的结点,如图所示: 方法一 方法描述 最简单粗暴地方法可以设置两个变量分别遍历两个链表,双重for循环,在循环遍历过程中,如果两个变量相等,那么两个...
  • /*判断两个链表是否交叉,如果交叉返回交叉节点,否则返回NULL。*/ Node* findCross(Node* head1,Node* head2) { if(head1==NULL||head2==NULL) return NULL; /*将第二个链表变成环链*/ Node* tail2=...
  • 一、解决这个问题之前我们需要了解下如何判断个链表有环? 下面提供二种方法进行实现: 使用快慢指针,p1为快指针,p2为慢指针,让这两个指针指向链表的头部,让p1每次走一步,p2每次走两步,如果p1和p2相交,...
  • 3.判断两个单链表是否相交?若相交,求出交点 ... 高频考察的大厂云图: ...如下面的两个链表: 在节点 c1 开始相交。 示例 1: 输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA
  • 一个比较经典的问题,判断两个链表是否相交,如果相交找出他们的交点。 思路: 1、碰到这个问题,第一印象是采用hash来判断,将两个链表的节点进行hash,然后判断出节点,这种想法当然是可以的。 2、当然采用...
  • 判断两个链表是否相交并找出交点

    千次阅读 2018-05-13 08:46:52
    问题描述:一个比较经典的问题,判断两个链表是否相交,如果相交找出他们的交点。思路:1、碰到这个问题,第一印象是采用hash来判断,将两个链表的节点进行hash,然后判断出节点,这种想法当然是可以的。2、当然采用...
  • 判断两个链表是否相交:(假设两个链表都没有环) 1、判断第一个链表的每个节点是否在第二个链表中 2、把第二个链表连接到第一个后面,判断得到的链表是否有环,有环则相交 3、先遍历第一个链表,记住最后一个...
  • (1)、两个链表都带环 分别获取两个链表环的入口点 判断入口点是否相同 如果入口点相同,临时修改链表为 Y 形状,处理完毕后恢复 如果入口点不相同,将一个环遍历一周看是否能遇到另外一个环的
  • 判断两个链表是否有交点 在1的基础上,求两个链表交点; 1. 判断两个链表是否有交点 总结了三种方法 利用hashset的方法 def has_insection_3(headA): """ 也可以使用hash_set, 如果 """ s = set() while...
  • 在上一篇文档中,通过java实现了单链表反转的问题,之后发现一个更有意思的问题就是如何判断两个链表是否相交?如果相交,则需要得到交点。 对于这个问题,需要分别考虑链表上是否存在环的情况。 //链表节点 public ...
  • 问题描述:一个比较经典的问题,判断两个链表是否相交,如果相交找出他们的交点。(注意两个单链表相交不会出现X型交叉——单链表,每个节点只有一个指针域)。第一种情况:两个链表均不含有环解题思路:1、直接法:...
  • 判断两个链表是否相交:(假设两个链表都没有环) 1、判断第一个链表的每个节点是否在第二个链表中 2、把第二个链表连接到第一个后面,判断得到的链表是否有环,有环则相交 3、先遍历第一个链表,记住最后一个节点,...
  • 判断两个单链表是否相交及找到第一个交点

    万次阅读 多人点赞 2017-12-24 16:45:48
    题目:给两个单链表,如何判断两个单链表是否相交?若相交,则找出第一个相交的节点。...因为两个链表一个共同节点,则这个节点里的指针域指向的下一个节点地址一样,所以下一个节点也会相交,依次类推。所以,若相
  • 两个链表都无环) (相交的特征:只要两条链表相交,则从第一个交点开始后面的节点都相交) 注:还要就链表是否有环的情况进行分类讨论。 (1)如果一个有环一个无环则肯定不相交 (2)都有环但是两个链表不...
  • 详解:寻找两个链表交点
  • 判断两个链表是否相交 题目描述 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。 题目数据 保证 整个链式结构中不存在环。 注意,函数返回...
  • 判断两个链表是否相交,若相交,求交点。(假设链表不带环)2.判断两个链表是否相交,若相交,求交点。(假设链表可能带环)【升级版】 2.【附加题】–请问下面的程序一共输出多少个“-”? #include #include ...
  • 前言 在前面两章有介绍过单链表的基本操作以及环链表的相关问题。本章主要分析两个单链表的交点问题。 首先声明,两个单链表只能存在 Y 型交叉,不会存在 X 型交叉。...两个链表环。 情况1 ...
  •  如果存在交点两个链表交点及其之后的部分是一致的-----这点很关键,一致的意思包括两部分:长度和内容。 struct Node { int data; struct Node * next; }; Node* FixIntersetion(Node* ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,446
精华内容 3,378
关键字:

如何判断两个链表是否有交点