Sponsored
Sponsored
First, traverse both linked lists to determine their lengths. Calculate the difference in lengths and advance the pointer of the longer list by the length difference. Then move both pointers in tandem to find the intersection node.
Time Complexity: O(m + n).
Space Complexity: O(1).
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9int getLength(struct ListNode *head) {
10 int length = 0;
11 while (head) {
12 length++;
13 head = head->next;
14 }
15 return length;
16}
17
18struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
19 int lenA = getLength(headA);
20 int lenB = getLength(headB);
21
22 if (lenA > lenB) {
23 for (int i = 0; i < lenA - lenB; i++)
24 headA = headA->next;
25 } else {
26 for (int i = 0; i < lenB - lenA; i++)
27 headB = headB->next;
28 }
29
30 while (headA != headB) {
31 headA = headA->next;
32 headB = headB->next;
33 }
34 return headA;
35}This solution first determines the lengths of both lists. It advances the pointer for the longer list by the difference in lengths. Then, it compares nodes in both lists step by step to find the intersection.
Use two pointers, each starting at the head of one list. Traverse the list until a pointer reaches null, then start traversing the other list from the beginning. Repeat until the two pointers meet at the intersection node.
Time Complexity: O(m + n).
Space Complexity: O(1).
1#include <iostream>
2using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
if (!headA || !headB) return NULL;
ListNode* a = headA;
ListNode* b = headB;
while (a != b) {
a = a ? a->next : headB;
b = b ? b->next : headA;
}
return a;
}The C++ implementation uses two pointers which start at the heads of the linked lists. They switch to the other head when they reach the end of their current list. They will meet at the intersection node or end together if there is no intersection.