LeetCode刷题笔记（Intersection of Two Linked Lists）
继续刷链表的题，感觉还是有一定的棘手，下面和大家来分享一下经验吧！
题目如下：
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
begin to intersect at node c1.
Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
Example 2:
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.
Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.
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)。
解答如下：
方法一（“右对齐”比较）
分别遍历两个链表，计算得到各自的长度，然后求它们长度的差值，如果长度相等则对应位置一一比较即可，否则需将较长的那个链表的头指针向后移动这个差值的个数，再一一比较即可。
注：由于链表重叠部分是公共的，所以只需要判断指向第一个公共节点的指针是否相等就行，而不是去判断他们的 ->val 是否相等。
class Solution{
public:
ListNode *getIntersectionNode( ListNode *headA, ListNode *headB ) {
ListNode *curA = headA;
ListNode *curB = headB;
int lenA = GetLength(headA); //计算链表长度
int lenB = GetLength(headB);
if (!lenA || !lenB) //存在空链表则返回NULL
return NULL;
if (lenA < lenB) { //比较长度，并移动对应指针
for (int i = 0; i < lenB - lenA; i++)
curB = curB->next;
} else if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; i++)
curA = curA->next;
}
while (curA != NULL && curB != NULL && curA != curB) //比较对应位置的值
{ curA = curA -> next;
curB = curB -> next;}
if (curA != NULL && curB != NULL)
return curA;
else
return NULL;
}
int GetLength( ListNode *head ){ //计算链表长度函数
int count = 0;
while( head ){
count ++;
head = head -> next;
}
return count;
}
};
提交后的结果如下：
方法二（用链表的环形思想）
先让两条链表分别从各自的开头开始往后遍历，当其中一条遍历到末尾时，再让其跳到另一个条链表的开头继续遍历。两个指针最终会相等，而且只有两种情况，一种情况是在公共交点处相遇，另一种情况是在各自的末尾的空节点处相等。由于两个指针走过的路程相同，且为两个链表的长度之和，所以必然相等。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if( !headA || !headB ) return NULL;
ListNode *a = headA;
ListNode *b = headB;
while(a!=b){
a = a == NULL?headB : a->next;//当找到表A的尾部时，a就开始指向表B
b = b == NULL?headA : b->next;//b也一样，这样一定有一个先指向另一个表，也就使得二者的长度之差得到了补偿
//画一个链表图就非常的直观了
//第二轮迭代时，a和b所要遍历的剩余节点的数量都是一样的
//因此即使没有交集，当a遍历到结尾的NULL时，返回值也是正确的
}
return a;
}
};
提交后的结果如下：
方法三（用哈希表法）
先创建一个哈希表，其键为节点的指针，其值记录出现的指针（出现记为1，未出现记为0）。遍历一遍A表，用哈希表记录各节点指针，然后再遍历一遍B表，尝试找到第一公共节点指针，若没找到则返回NULL。
class Solution{
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){
unordered_map< ListNode * , int> record;
ListNode *a = headA;
ListNode *b = headB;
while( a != NULL ) //哈希表存储A链节点指针
{
record[a] = 1;
a = a -> next;
}
while( b != NULL )
{
if( record[b] == 1 ) //借助哈希表找到第一个公共节点的指针
return b;
else
b = b ->next;
}
return NULL;
}
};
日积月累，与君共进，增增小结，未完待续。