公明做网站,湖南岳阳网站建设公司黄页顺企网,网站空间怎么做,it外包考核leetcode 160题#xff0c;判断两个链表是否相交
此题可以说是算法界第一深情#xff0c;如果我走过你走过的路#xff0c;那么我们就可能会相遇。
具体解决思路如下
两个链表是否相交有两种可能#xff0c;一种不相交#xff0c;一种相交#xff0c;首先来看下相交的… leetcode 160题判断两个链表是否相交
此题可以说是算法界第一深情如果我走过你走过的路那么我们就可能会相遇。
具体解决思路如下
两个链表是否相交有两种可能一种不相交一种相交首先来看下相交的情况那么它们会有公共部分假设公共部分长度为c,然后链表一中不想交部分为a, 链表二中不想交部分为b,那么链表一的长度可以表示为a c, 链表2的长度为b c, 想在弄两个指针一个指针A指向链表一的头部另一个指针B指向链表b的头部两个指针向后遍历如果到达了尾部那么就从另一个链表的头部开始遍历直到两个节点相同即找到了交叉节点那么指针A就走过了ac b的长度指针B走过了bc a的长度可以看到它们是一样大的所以可以找到相同的节点同理如果两个链表不想交那么都走完两个链表后节点都为null代表没有交点。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode tempA headA;ListNode tempB headB;while(tempA ! tempB){tempA tempA null ? headB : tempA.next;tempB tempB null ? headA : tempB.next;}return tempA;}
}
具体代码如下
