首页 > 代码库 > leetcode[160] Intersection of Two Linked Lists
leetcode[160] Intersection of Two Linked Lists
那几题要15刀才能测试的就先放着了。先吧可以在线测试的刷了。
这题是找到零个链表的相交的那个节点。如果没有相交，那就返回NULL。
思路一：
如果有相交，那么他们相交点之后的节点肯定都是共有的，然后两个链表有长有短的话，就先把长的读到和短的一样长，然后两个人在同时走，走到第一个相同的点就是答案了。如果相同的点是NULL了，那就是没有相交点。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *l1 = headA, *l2 = headB; if (!headA || !headB) return NULL; int cnt1 = 0, cnt2 = 0; while(l1) { cnt1++; l1 = l1 -> next; } while(l2) { cnt2++; l2 = l2 -> next; } if (cnt1 > cnt2) { l1 = headA; l2 = headB; int tmpcnt1 = cnt1 - cnt2; while(tmpcnt1-- > 0) l1 = l1 -> next; } else { l2 = headB; l1 = headA; int tmpcnt2 = cnt2 - cnt1; while(tmpcnt2-- > 0) l2 = l2 -> next; } while(l1 && l2 && l1 != l2) { l1 = l1 -> next; l2 = l2 -> next; } if (l1 == l2) return l1; return NULL; }};
思路二：
因为两个链表长度可能不一样长，所以不能从第一次走一样的距离判断相交点，但是。可以这样，两个链表同时走，走到末尾后，分别将指针跳到另一个链表的开头，这样，他们第一次相同的点就是答案了。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *l1 = headA, *l2 = headB; if (!headA || !headB) return NULL; while(l1 && l2) { l1 = l1 -> next; l2 = l2 -> next; } if (!l1) { l1 = headB; while(l1 && l2) { l1 = l1 -> next; l2 = l2 -> next; } l2 = headA; while(l1 && l2 && l1 != l2) { l1 = l1 -> next; l2 = l2 -> next; } } else { l2 = headA; while(l1 && l2) { l1 = l1 -> next; l2 = l2 -> next; } l1 = headB; while(l1 && l2 && l1 != l2) { l1 = l1 -> next; l2 = l2 -> next; } } if (l1 != l2) return NULL; return l1; }};
leetcode[160] Intersection of Two Linked Lists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。