> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/01-10-2022-160.md).

# 01/10/2022 160

brutal force 

for each node in list A, travers over list B and check if it is in list B. 

Time O(N \* M), Space O(1)

```
// Some code

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //Brutal force
        while (headA != null){
            ListNode p = headB;
            while (p != null){
                if (headA == p ) return headA;
                p = p.next;
            }
            headA = headA.next;
        }
        return null;
    }
}
```

//The one thing we need to be careful of is that we're comparing objects of type Node. We don't want to compare the values within the nodes; doing this would cause our code to break when two different nodes have the same value.

//

1. Calculate N: the length of list A.
2. Calculate M; the length of list B.
3. Set the start pointer for the *longer* list.
4. Step the pointers through the list together.

If they have intersection, it must be in the tail. (shorter length of the Linkedlist)

```
// Some code
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       ListNode pA = headA;
       ListNode pB = headB;
       int lengthA = 0;
       int lengthB = 0;
        
       while (pA != null){
           lengthA++;
           pA = pA.next;
       }
        
        while (pB != null){
            lengthB++;
            pB = pB.next;
        }
        pA = headA;
        pB = headB;
        
        if (lengthA > lengthB){
            for (int i = 0; i < lengthA - lengthB; i++){
                if (pA == pB) return pA;
                pA = pA.next;
            }
        } else {
            for (int i = 0; i < lengthB - lengthA; i++){
                if (pA == pB) return pA;
                pB = pB.next;
            }
        }
        
        while (pA != pB){
            pA = pA.next;
            pB = pB.next;
        }
        
        return pA;
    }
}
```

Clean the code a little bit!

//Time O(n + m) Space O(1)

```
// Some code
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       ListNode pA = headA;
       ListNode pB = headB;
       int lengthA = 0;
       int lengthB = 0;
        
       while (pA != null){
           lengthA++;
           pA = pA.next;
       }
        
        while (pB != null){
            lengthB++;
            pB = pB.next;
        }
        pA = headA;
        pB = headB;
        
        for (int i = 0; i < Math.abs(lengthA - lengthB); i++){
                if (pA == pB) return pA;
                 if (lengthA > lengthB) {pA = pA.next;}
                 else {pB = pB.next;}         
        }
       
        
        while (pA != pB){
            pA = pA.next;
            pB = pB.next;
        }
        
        return pA;
    }
}
```

public class Solution {&#x20;

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {&#x20;

while (headA != null) {&#x20;

&#x20;   ListNode pB = headB;&#x20;

&#x20;    while (pB != null) {&#x20;

&#x20;      if (headA == pB) return headA;&#x20;

&#x20;      pB = pB.next;&#x20;

&#x20;    } headA = headA.next;&#x20;

&#x20;    } return null;

&#x20;}&#x20;

}

![](/files/2Sx9vyR3fbAGZ7wQrM27)

//optimized using hashtable to store listB node

Time O(n + m) Space O(n)

//hashtable //put node in listB in hashtable //traverse list A to check if the node is in the hashtable //Time O(N + M), Space O（M） public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { Set nodesInB = new HashSet();

```
    while (headB != null) {
        nodesInB.add(headB);
        headB = headB.next;
    }

    while (headA != null) {
        // if we find the node pointed to by headA,
        // in our set containing nodes of B, then return the node
        if (nodesInB.contains(headA)) {
            return headA;
        }
        headA = headA.next;
    }

    return null;
}


```

}

The best one:&#x20;

```
// Some code
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       ListNode pA = headA;
       ListNode pB = headB;
       
        // A + C+ B = B + C + A
        while (pA != pB){
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        
        return pA;
    }
}
```