编写一个程序,找到两个单链表相交的起始节点。
注意:
如果两个链表没有交点,返回 null.
在返回结果后,两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。
思路
两条链表长度相减,得到长度之差count,再让长的链表走count步,然后两条链表同时走,即可得到相交的节点
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a=headA;
ListNode b=headB;
int lenA=0,lenB=0;
while(a!=null){
a=a.next;
lenA++;
}
while(b!=null){
b=b.next;
lenB++;
}
int count=0;
if(lenA>=lenB){
count=lenA-lenB;
for(int i=0;i<count;++i){
headA=headA.next;
}
}else{
count=lenB-lenA;
for(int i=0;i<count;++i){
headB=headB.next;
}
}
while(headA!=headB){
headA=headA.next;
headB=headB.next;
}
return headA;
}
}
网友评论