-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathleetcode160.cpp
128 lines (120 loc) · 3.38 KB
/
leetcode160.cpp
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/*************************************************
Author: wenhaofang
Date: 2023-03-12
Description: leetcode160 - Intersection of Two Linked Lists
*************************************************/
#include <bits/stdc++.h>
using namespace std;
/**
* 方法一：栈
*
* 理论时间复杂度：O(m + n)，其中 m、n 为两个链表的长度
* 理论空间复杂度：O(m + n)，其中 m、n 为两个链表的长度
*/
/**
* 思路
*
* 分别遍历两个链表，将其存入栈中，然后同时出栈，判断节点是否相同
*
* 如果相同，则说明是相交部分，如果不同，则说明是分叉部分
*/
// struct ListNode {
// int val;
// ListNode *next;
// ListNode(int x) : val(x), next(NULL) {}
// };
// class Solution {
// public:
// ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// if (headA == nullptr) {
// return nullptr;
// }
// if (headB == nullptr) {
// return nullptr;
// }
// stack<ListNode*> stackA;
// stack<ListNode*> stackB;
// while (headA != nullptr) {
// stackA.push(headA);
// headA = headA -> next;
// }
// while (headB != nullptr) {
// stackB.push(headB);
// headB = headB -> next;
// }
// ListNode* ans = nullptr;
// while (!stackA.empty() && !stackB.empty()) {
// ListNode* currA = stackA.top();
// ListNode* currB = stackB.top();
// if (currA == currB) {
// ans = currA;
// stackA.pop();
// stackB.pop();
// } else break;
// }
// return ans;
// }
// };
/**
* 方法二：数学
*
* 理论时间复杂度：O(m + n)，其中 m、n 为两个链表的长度
* 理论空间复杂度：O(1)
*/
/**
* 思路
*
* 初始化指针在两个链表开头并同时向前走
*
* 当 A 指针到达末尾时，将其指向 B 开头
*
* 当 B 指针到达末尾时，将其指向 A 开头
*
* 当二者相遇在某一节点时就是答案
*/
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == nullptr) {
return nullptr;
}
if (headB == nullptr) {
return nullptr;
}
ListNode* currA = headA;
ListNode* currB = headB;
while (currA != currB) {
currA = currA == nullptr ? headB : currA -> next;
currB = currB == nullptr ? headA : currB -> next;
}
return currA;
}
};
/**
* 测试
*/
int main() {
Solution* solution = new Solution();
ListNode* c3 = new ListNode(5);
ListNode* c2 = new ListNode(4);
ListNode* c1 = new ListNode(8);
ListNode* b3 = new ListNode(1);
ListNode* b2 = new ListNode(6);
ListNode* b1 = new ListNode(5);
ListNode* a2 = new ListNode(1);
ListNode* a1 = new ListNode(4);
a1 -> next = a2;
a2 -> next = c1;
b1 -> next = b2;
b2 -> next = b3;
b3 -> next = c1;
c1 -> next = c2;
c2 -> next = c3;
ListNode* ans = solution -> getIntersectionNode(a1, b1);
cout << ans -> val << endl;
}