面试题 02.07. 链表相交
解题思路
1.分析题意，两个链表时末尾相交，也就是说，只要知道两个链表从后往前最初的相等元素即可
2.求链表A的长度、 求链表B的长度
3.让curA为最长链表的头，lenA为其长度
4.求长度差，让curA和curB在同一起点上（末尾位置对齐）
5.遍历curA 和 curB，遇到相同则直接返回
解题遇到的问题
无
后续需要总结学习的知识点
能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？
##解法
class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0, lenB = 0;
while (curA != null) { // 求链表A的长度
lenA++;
curA = curA.next;
}
while (curB != null) { // 求链表B的长度
lenB++;
curB = curB.next;
}
curA = headA;
curB = headB;
// 让curA为最长链表的头，lenA为其长度
if (lenB > lenA) {
// 1. swap (lenA, lenB);
int tmpLen = lenA;
lenA = lenB;
lenB = tmpLen;
// 2. swap (curA, curB);
ListNode tmpNode = curA;
curA = curB;
curB = tmpNode;
}
// 求长度差
int gap = lenA - lenB;
// 让curA和curB在同一起点上（末尾位置对齐）
while (gap-- > 0) {
curA = curA.next;
}
// 遍历curA 和 curB，遇到相同则直接返回
while (curA != null) {
if (curA == curB) {
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
}
