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 <iostream>
2using namespace std;
3
4struct ListNode {
5 int val;
6 ListNode* next;
7 ListNode(int x) : val(x), next(NULL) {}
8};
9
10int getLength(ListNode* head) {
11 int length = 0;
12 while (head) {
13 length++;
14 head = head->next;
15 }
16 return length;
17}
18
19ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
20 int lenA = getLength(headA);
21 int lenB = getLength(headB);
22
23 if (lenA > lenB) {
24 for (int i = 0; i < lenA - lenB; i++) headA = headA->next;
25 } else {
26 for (int i = 0; i < lenB - lenA; i++) headB = headB->next;
27 }
28
29 while (headA != headB) {
30 headA = headA->next;
31 headB = headB->next;
32 }
33 return headA;
34}This solution uses the same logic as the C version. The getLength function is used to determine the lengths of the input linked lists. Adjust both head pointers depending on which list is longer and 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
This implementation uses two pointers initialized to the heads of the two lists. Each pointer traverses its list and switches to the other list once it reaches the end. They meet at the intersection node or at null if there is none.