-
题目：
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
begin to intersect at node c1.
Notes:
If the two linked lists have no intersection at all, return null
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.
-
分析：
两个链表，如图会从某个位置开始进行重合，求出这个起始交点，需要注意的是：- 没有交点，返回NULL
- 保持原来的结构不变
- 确保没有环
- 时间复杂度为O（n），空间复杂度为O（1）
其中第一条和最后一条注意事项是最重要的，个人觉得这道题虽然在LeetCode上面是easy难度的，但是涉及到的内容还是挺不少的，因为有最后一条注意事项的限制，所以需要结合时间复杂度和空间复杂度来进行算法定制，对于本题，本文一共会列出三种算法来求解，并同时分析算法复杂度和时间复杂度。
-
三种算法的分析：
-
直接法：
遍历链表A，对于每一个遍历的节点都遍历一次链表B，判断是否有节点相同，这种算法是最简单的，但是效率不高
- 时间复杂度：O（n * n）
- 空间复杂度：O（1）
显然是不能满足要求的，时间复杂度不是一个级别的
-
哈希表求解法
先遍历链表A，将链表A的每个节点放入哈希表中，然后遍历链表B，对于每个节点都利用哈希表进行判断，看是否存在相同的节点
- 时间复杂度：O（n）
- 空间复杂度：O（n）
这里时间复杂度是满足了O（n），但是空间复杂度却由于创建了哈希表而变成了O（n）
-
双指针求解法
两个链表的长度是不一样的，但是重叠部分是一样的，也就是说后半部分是一样的，那么就可以将长的链表的前半部分给裁剪了，然后将裁剪后的链表的起始节点作为第一个节，然后同时遍历两个链表进行判断是否相同，所以时间复杂度仅仅为O（n）
- 时间复杂度：O（n）
- 空间复杂度：O（1）
这就是最符合题目的求解方法，从这道题也能看出来算法的重要性，他能够提高空间和时间的效率
-
直接法：
代码：
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *nodeA = headA;
ListNode *nodeB = headB;
int lengthA = 0;
int lengthB = 0;
while(headA) {
lengthA++;
headA = headA->next;
}
while(headB) {
lengthB++;
headB = headB->next;
}
if (lengthA >= lengthB) {
int difference = lengthA - lengthB;
for (int i = 0; i < difference; i++) {
nodeA = nodeA->next;
}
} else {
int difference = lengthB - lengthA;
for (int i = 0; i < difference; i++) {
nodeB = nodeB->next;
}
}
while(nodeA!=nodeB) {
nodeA = nodeA->next;
nodeB = nodeB->next;
}
return nodeA;
}
