**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.**

We can solve this question by 2 steps:
1. Before traversing the linked list, compare the length of each linked list, and adjust the pointer of the longer one, so that there are same number of nodes left after the pointers.
2. Traverse the linked lists together. Each time compare whether the address of two nodes from List A and List B are the same.

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = getLength(headA);
int lenB = getLength(headB);
int lenDiff = 0;
ListNode curA = headA;
ListNode curB = headB;
if (lenA > lenB) {
lenDiff = lenA - lenB;
while (lenDiff > 0 ) {
curA = curA.next;
lenDiff--;
}
} else {
lenDiff = lenB - lenA;
while (lenDiff > 0) {
curB = curB.next;
lenDiff--;
}
}
/*Only after adjusting the starting point, can we traverse two linked list together */
while (curA != null) {
if (curA == curB) {
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
public int getLength (ListNode head) {
ListNode cur = head;
int len = 0;
if (head == null)
return 0;
while (cur != null) {
cur = cur.next;
len++;
}
return len;
}

### Like this:

Like Loading...

*Related*