> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/linked_list/2-pointers-with-one-first-moved-n-steps/intersection-of-two-linked-lists.md).

# 160. Intersection of Two Linked Lists

> Write a program to find the node at which the intersection of two singly linked lists begins.
>
> 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.

## Thoughts

找到两个链表开始相交的点。两个链表如果等长，那两个指针一起往前走当相遇时就是交点。为了让长链表指针抛去多余的，让两个指针分别从两个头一起走，当其中一个撞到null时另一个到null的距离就是长的比短的多出去的部分。再让一个指针cur从长的头开始和剩下那个没撞到null的指针一起遍历直到撞到null，此时cur所在位置就是长的抛去多余的后所在位置。

## Code

```
/*
 * @lc app=leetcode id=160 lang=cpp
 *
 * [160] Intersection of Two Linked Lists
 */

// @lc code=start
/**
 * 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 *cur_a = headA, *cur_b = headB;  
        while (cur_a != nullptr && cur_b != nullptr) {
            cur_a = cur_a->next;
            cur_b = cur_b->next;
        }
        ListNode *cur, *cur2, *flag;
        if (cur_a == nullptr) {
            cur = headB; 
            cur2 = headA; 
            flag = cur_b;
        } else {
            cur = headA; 
            cur2 = headB; 
            flag = cur_a;
        }
        while (flag != nullptr) {
            flag = flag->next;
            cur = cur->next;
        }
        while (cur != cur2) {
            cur = cur->next;
            cur2 = cur2->next;
        }
        return cur;
    }
};
// @lc code=end


```

```
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto len_a = len(headA), len_b = len(headB);
        auto head_a = headA, head_b = headB;
        if (len_a < len_b) {
            head_a = headB;
            head_b = headA;
        }
        for (int i = 0; i < abs(len_a - len_b); ++i) {
            head_a = head_a->next;
        }
        while (head_a != head_b) {
            head_a = head_a->next;
            head_b = head_b->next;
        }
        return head_a;
    }

private:
    int len(ListNode *head) {
        int res = 0;
        while (head != NULL) {
            head = head->next;
            ++res;
        }
        return res;
    }
};
```

```
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int lenA = 0, lenB = 0;
        ListNode node = headA;
        while (node.next != null) {
            lenA++;
            node = node.next;
        }
        node = headB;
        while (node.next != null) {
            lenB++;
            node = node.next;
        }
        if (lenA < lenB) {
            for (int i = 0; i < lenB - lenA; i++) {
                headB = headB.next;
            }
        } else {
            for (int i = 0; i < lenA - lenB; i++) {
                headA = headA.next;
            }
        }

        while (headA != null && headB != null) {
            if (headA == headB) {
                return headB;
            }
            headA = headA.next;
            headB = headB.next;
        }

        return null;
    }
}
```

## Analysis

时间复杂度O(m+n).

还想到了另一种解法，把B的尾和A连上，环开始的点就是交叉点。