Intersection of Two Linked Lists

Nov 02, 2017



今天的题目是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:

A:          a1  a2
                     c1  c2  c3
B:     b1  b2  b3

begin to intersect at node c1.


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) {
    vector<ListNode *> vec;
    while(headA) {
        headA = headA->next;
    while(headB) {
        if (find(vec.begin(),vec.end(),headB) != vec.end()) return headB;
        headB = headB->next;
    return nullptr;


A:          a1  a2
                     c1  c2  c3
B:     b1  b2  b3


ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    //if (headA == nullptr || headB == nullptr) return nullptr;
    ListNode *end = nullptr;
    while(1) {
        if (headA == end || headB == end) return end;
        ListNode *pa = headA;
        ListNode *pb = headB;
        while(pa->next != end) pa = pa->next;
        while(pb->next != end) pb = pb->next;
        if (pa != pb) return end;
        else end = pa;


ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *cur1 = headA, *cur2 = headB;
    while(cur1 != cur2){
        cur1 = cur1?cur1->next:headB;
        cur2 = cur2?cur2->next:headA;
    return cur1;




Kth Largest Element in an array

Number of Islands

comments powered by Disqus