leetcode算法题--相交链表
原题链接：
1、set
用set先保存一个链表的所有节点，然后判断另外一个链表的节点是否在其中
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
set<ListNode*> st;
ListNode *p=headA;
while(p){
st.insert(p);
p=p->next;
}
p=headB;
while(p){
if(st.count(p)) return p;
p=p->next;
}
return NULL;
}
2、双指针
- 指针 pA指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
- 如果 pA到了末尾，则 pA = headB 继续遍历
- 如果 pB到了末尾，则 pB = headA 继续遍历
- 直到两指针相遇，否则不会相遇
如图（）：
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p=headA,*q=headB;
while(p!=q){
p=p!=NULL?p->next:headB;//到了末尾则指向B
q=q!=NULL?q->next:headA;//到了末尾则指向A
}
return p;
}
上一篇：
IDEA上Java项目控制台中文乱码