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:
- Calculate Lengths: First, calculate the lengths of both linked lists.
- Align Start Pointers: If one list is longer than the other, advance its pointer to align the lengths of both lists.
- 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;
}
}
public class LinkedList {
// Function to get the intersection node of two linked lists
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
// Calculate the lengths of both linked lists
int lengthA = getLength(headA);
int lengthB = getLength(headB);
// Align the start of both lists
while (lengthA > lengthB) {
headA = headA.next;
lengthA--;
}
while (lengthB > lengthA) {
headB = headB.next;
lengthB--;
}
// Traverse both lists together to find the intersection
while (headA != headB) {
headA = headA.next;
headB = headB.next;
}
return headA; // or headB, they are the same at intersection point
}
// Utility function to calculate the length of a linked list
private int getLength(ListNode head) {
int length = 0;
while (head != null) {
length++;
head = head.next;
}
return length;
}
// Function to print the linked list
public void printList(ListNode head) {
ListNode temp = head;
while (temp != null) {
System.out.print(temp.val + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
// Create two linked lists
// List A: 1 -> 3 -> 5 -> 7 -> 9 -> 11
ListNode headA = new ListNode(1);
headA.next = new ListNode(3);
headA.next.next = new ListNode(5);
headA.next.next.next = new ListNode(7);
headA.next.next.next.next = new ListNode(9);
headA.next.next.next.next.next = new ListNode(11);
// List B: 2 -> 4 -> 9 -> 11
ListNode headB = new ListNode(2);
headB.next = new ListNode(4);
headB.next.next = headA.next.next.next.next; // 9
headB.next.next.next = headA.next.next.next.next.next; // 11
System.out.println("List A:");
list.printList(headA);
System.out.println("List B:");
list.printList(headB);
// Find intersection
ListNode intersection = list.getIntersectionNode(headA, headB);
if (intersection != null) {
System.out.println("Intersection at node with value: " + intersection.val);
} else {
System.out.println("No intersection.");
}
}
}
Explanation:
-
ListNode Class:
- Represents each node in the linked list with a value (
val) and a pointer to the next node (next).
- Represents each node in the linked list with a value (
-
getIntersectionNode Method:
-
Calculate Lengths: The lengths of both linked lists are calculated using the
getLengthmethod. - 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.
-
Calculate Lengths: The lengths of both linked lists are calculated using the
-
getLength Method:
- A helper method to calculate the length of a linked list.
-
printList Method:
- A utility function to print the nodes of the linked list.
-
main Method:
-
Create two linked lists: For example,
1 -> 3 -> 5 -> 7 -> 9 -> 11and2 -> 4 -> 9 -> 11, where the intersection starts at node9. -
Find and print the intersection: The program will output
9as the intersection point.
-
Create two linked lists: For example,
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.
Top comments (0)