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.

```/*

public class Node {
int val;
Node next;
Node(int x) { val = x; }
}
*/

public class Solution {

}
}```

This problem is selected from LeetCode.

Solution

Solution1: first find the length of the two linked list and get the length difference. Then traverse the longer linked list and
move length difference steps first. Then traverse the two lists at the same time until a common node is found.

```public class Solution {

return null;

int lenA=0;
int lenB=0;

// get the length of A and B
lenA++;
}
lenB++;
}

// move the head of the longer
// list the length difference steps
while(lenA>lenB){
lenA--;
}
while(lenB>lenA){
lenB--;
}

// until a common node is found.
}

// point to the same node
// or both are null

}
}```

The solution needs O(m+n) time and O(1) space.

Solution2: For both lists, connect the end of one list to the head of the other (like the digit 8). Then use two pointers to scan
both lists. For each list once it reaches the end, continue scanning the other list. Once the two runner equal to each other, return the position

```public class Solution {