-
Notifications
You must be signed in to change notification settings - Fork 0
/
IntersectionofTwoLinkedLists.hpp
98 lines (81 loc) · 1.77 KB
/
IntersectionofTwoLinkedLists.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//Intersection of Two Linked Lists
//
//Write a program to find the node at which the intersection of two singly linked lists begins.
//
//
//For example, the following two linked lists :
//
// A : a1 ¡ú a2
// ¨K
// c1 ¡ú c2 ¡ú c3
// ¨J
//B : b1 ¡ú b2 ¡ú b3
// begin to intersect at node c1.
//
//
//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.
#include "LinkList.hpp"
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
if (nullptr == headA || nullptr == headB)
return nullptr;
size_t length_A = getLength(headA);
size_t length_B = getLength(headB);
size_t distance = length_A > length_B ?
length_A - length_B :
length_B - length_A;
ListNode* p = headA;
ListNode* q = headB;
if (length_A > length_B)
p = forwardNStep(headA, distance);
else
q = forwardNStep(headB, distance);
while (nullptr != p && nullptr != q && p != q)
{
p = p->next;
q = q->next;
}
if (p == q)
return p;
}
ListNode* forwardNStep(ListNode* head, size_t n)
{
if (0 == n)
return head;
ListNode* p = head;
while (0 != n && nullptr != p)
{
n--;
p = p->next;
}
return p;
}
size_t getLength(ListNode* head)
{
if (nullptr == head)
return 0;
ListNode* p = head;
int length = 0;
while (nullptr != p)
{
length++;
p = p->next;
}
return length;
}
};