---
title: 'LeetCode 160. Intersection of Two Linked Lists'
disqus: hackmd
---

# LeetCode 160. Intersection of Two Linked Lists

## Description

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

## Example

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

## Constraints

The number of nodes of listA is in the m.
The number of nodes of listB is in the n.
1 <= m, n <= 3 * 10^4^
1 <= Node.val <= 10^5^
0 <= skipA < m
0 <= skipB < n
intersectVal is 0 if listA and listB do not intersect.
intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

## Answer
方法1
此題可用雙迴圈一一比對法，有用但太久時間。

// 2021_10_30
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB){
    if(headA == NULL){return NULL;}
    if(headB == NULL){return NULL;}
    while(headA != NULL){
        struct ListNode *temp = headB;
        while(temp != NULL){
            if(headA == temp){return headA;}
            temp = temp->next;
        }
        headA = headA->next;
    }
    return NULL;
}

方法2
先計算兩list長度並記錄最後一點，若最後一點相同代表兩list有接在一起，然後計算兩長度差將較長者往下移動到兩list一樣長的位置，最後就可以同時一一往下移動檢查是否相同。

// 2021_10_30
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB){
    if(headA == NULL){return NULL;}
    if(headB == NULL){return NULL;}
    struct ListNode *tempA = headA, *tempB = headB, *lastA = NULL, *lastB = NULL;
    int cntA = 0, cntB = 0, offset = 0;
    while(tempA != NULL){
        cntA++;
        lastA = tempA;
        tempA = tempA->next;
    }
    while(tempB != NULL){
        cntB++;
        lastB = tempB;
        tempB = tempB->next;
    }
    if(lastA == lastB){
        for(offset = 0; offset<(cntA - cntB); offset++){headA = headA->next;}
        for(offset = 0; offset<(cntB - cntA); offset++){headB = headB->next;}
        while(headA != headB){
            headA = headA->next;
            headB = headB->next;
        }
        return headA;
    }
    return NULL;
}

方法2-1 也可以不檢查最終點是否相同，直接一一往下推做比較。

//2022_03_12
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB){
    int lena = 0, lenb = 0;
    struct ListNode *opa = headA, *opb = headB;
    while(opa!=NULL){opa = opa->next; lena++;}
    while(opb!=NULL){opb = opb->next; lenb++;}
    for(int i = 0; i<lena-lenb; i++){headA = headA->next;}
    for(int i = 0; i<lenb-lena; i++){headB = headB->next;}
    while(headA!=NULL && headB!=NULL){
        if(headA==headB){return headA;}
        headA = headA->next;
        headB = headB->next;
    }
    return NULL;
}

## Link
https://leetcode.com/problems/intersection-of-two-linked-lists/
###### tags: `Leetcode`