# 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连上，环开始的点就是交叉点。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/linked_list/2-pointers-with-one-first-moved-n-steps/intersection-of-two-linked-lists.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.