Leetcode 160 Intersection of Two Linked Lists
Leetcode 160 Intersection of Two Linked Lists
triplebee
发布于 2018-01-12 14:51:30
发布于 2018-01-12 14:51:30
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 → b3begin 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.
找出两个链表的交叉点，
先跑一边得到链表的长度差，因为最后相同部分的长度相同，所以只要让长的链表先走完长度差，然后同时走，必然会在交叉点处相遇。
不难写，只是自己写得太丑，看看人家的，多简洁。
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
ListNode *p1 = headA;
ListNode *p2 = headB;
if (p1 == NULL || p2 == NULL) return NULL;
while (p1 != NULL && p2 != NULL && p1 != p2) {
p1 = p1->next;
p2 = p2->next;
if (p1 == p2) return p1;
if (p1 == NULL) p1 = headB;
if (p2 == NULL) p2 = headA;
}
return p1;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016-12-29 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读