Shivam Tyagi

Posted on

# How to find intersection of two singly linked lists in a simple and optimal way in java

To find the intersection of two singly linked lists in a simple and optimal way, you can use the following approach. The key idea is to align the ends of both linked lists by adjusting the start point of the longer list, and then traverse both lists simultaneously to find the intersection point.

### Steps:

1. Calculate Lengths: First, calculate the lengths of both linked lists.
2. Align Start Pointers: If one list is longer than the other, advance its pointer to align the lengths of both lists.
3. Find Intersection: Traverse both lists simultaneously. The first node where they meet is the intersection point.

### Java Implementation:

``````class ListNode {
int val;
ListNode next;

ListNode(int val) {
this.val = val;
this.next = null;
}
}

// Function to get the intersection node of two linked lists
return null;
}

// Calculate the lengths of both linked lists

// Align the start of both lists
while (lengthA > lengthB) {
lengthA--;
}

while (lengthB > lengthA) {
lengthB--;
}

// Traverse both lists together to find the intersection
}

return headA;  // or headB, they are the same at intersection point
}

// Utility function to calculate the length of a linked list
int length = 0;
length++;
}
return length;
}

// Function to print the linked list
while (temp != null) {
System.out.print(temp.val + " ");
temp = temp.next;
}
System.out.println();
}

public static void main(String[] args) {

// List A: 1 -> 3 -> 5 -> 7 -> 9 -> 11

// List B: 2 -> 4 -> 9 -> 11

System.out.println("List A:");

System.out.println("List B:");

// Find intersection

if (intersection != null) {
System.out.println("Intersection at node with value: " + intersection.val);
} else {
System.out.println("No intersection.");
}
}
}
``````

### Explanation:

1. ListNode Class:

• Represents each node in the linked list with a value (`val`) and a pointer to the next node (`next`).
2. getIntersectionNode Method:

• Calculate Lengths: The lengths of both linked lists are calculated using the `getLength` method.
• Align Start Pointers: If the lists have different lengths, the longer list's pointer is advanced to align with the shorter list's pointer.
• Traverse Together: Both pointers are then moved simultaneously. The first node where they match is the intersection node.
3. getLength Method:

• A helper method to calculate the length of a linked list.
4. printList Method:

• A utility function to print the nodes of the linked list.
5. main Method:

• Create two linked lists: For example, `1 -> 3 -> 5 -> 7 -> 9 -> 11` and `2 -> 4 -> 9 -> 11`, where the intersection starts at node `9`.
• Find and print the intersection: The program will output `9` as the intersection point.

### Complexity:

• Time Complexity: ( O(m + n) ), where ( m ) and ( n ) are the lengths of the two linked lists. The lists are traversed a maximum of twice.
• Space Complexity: ( O(1) ), since only a few extra pointers are used.

This method is simple and optimal, ensuring that you find the intersection point of two singly linked lists in an efficient manner.