1.老老实实解
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0,lenB = 0;
//计算链表A的长度
while(curA!=null){
lenA++;
curA = curA.next;
}
//计算链表B的长度
while(curB!=null){
lenB++;
curB = curB.next;
}
//初始化为头节点
curA = headA;
curB = headB;
//无论如何保证链表A的长度最大,不是的话就将两个链表交换
if(lenB>lenA){
//交换链表长度
int temp = lenB;
lenB = lenA;
lenA = temp;
//交换两个链表
ListNode tmp = curB;
curB = curA;
curA = tmp;
}
//计算差值
int gap = lenA - lenB;
//让他们保持尾部对齐
while(gap-->0){
curA = curA.next;
}
//两个链表一起向后移找到相同结点
while(curA!=null){
if(curA==curB){
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}
2.巧解
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
while(curA!=curB){
curA = curA==null?headB:curA.next;
curB = curB==null?headA:curB.next;
}
return curA;//返回curA,curB都行
}
}
两种方法的执行用时和内存消耗都一样