intersection of two linked lists.(两个链表交叉的地方)

时间:2021-05-14 06:27:55

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2

c1 → c2 → c3

B: b1 → b2 → b3

求两个链表开始重合的地方,也就是交叉的地方。。

思路:两个链表从交叉的位置开始,后面的长度是相同的,前面的长度可能相等也可能不同。当前面长度也相同,也就是两个链表长度相同时,就一一对应比较,找出相同的节点。长度相同时,只有一一对应的位置才可能相同,交错的位置上节点是不可能相同的,因为若交错的位置节点相同,那么后面长度要相同,因为出现交错,前面长度就不相同了,所以不行。。。当两个链表长度不相同时,从交叉点开始,后面长度相等,所以只有交叉点前面长度会不同,而这对求交叉点没有影响,我们只要跳过长链表的头上几个节点,使前面长度也相同,这样就可以开始一一对应比较了,只有长度相同才可以一一对应比较。而长链表前面比短链表多出来的几个节点对求交叉点是没有影响的(如上面的b1)。交叉点是不会出现在那几个节点中的,因为如果出现在那里,这样交叉点以后都是重复的,这样重复的节点个数都大于短链表的节点个数了。

/**
* 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) {
/*
思路:求出两个链表的长度,如果长度不一样,那么将长的那个链表头几个节点跳过,直接跳到长度相等的部分,然后开始一一对应比较。
因为长的链表多出来的几个是多余的,他们在头上,是不会和另一链表重复的,如果重复,两个链表的长度就应该相同了。
如果长度相同了,就一一对应比较,只有对应位置才可能相等,如果错开相等,那么长度就不相同了,因为从相等的元素开始,后面的长度是相同的(重合)。
如果前面的长度不同,就直接跳到长度相同的地方在比较
*/ int lenA=length(headA),lenB=length(headB); //从头开始移到长度相同的位置,因为多出来的那些元素是不会出现相等的,如果出现相等(就开始重合),长度就比另一个链表长了,这是不正确的。
while(lenA<lenB){
headB=headB.next;
lenB--;
} while(lenA>lenB){
headA=headA.next;
lenA--;
}
//长度相同,开始一一比对
while(headA!=headB){
headA=headA.next;
headB=headB.next;
}
//如果没有重合的,一直到最后,headA和headB都会为空了,上面也会跳出循环
return headA;
} public int length(ListNode node){
int length=0;
while(node!=null){
length++;
node=node.next;
}
return length;
}
}