Skip to content

Commit c09b621

Browse files
chefyuanchefyuan
authored
Merge pull request chefyuan#21 from coderhare/main
链表专题更新cpp代码
2 parents 6d96954 + afd452a commit c09b621

15 files changed

+626
-11
lines changed

‎animation-simulation/链表篇/234. 回文链表.md

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,8 @@
3333

3434
我们首先将链表的所有元素都保存在数组中，然后再利用双指针遍历数组，进而来判断是否为回文。这个方法很容易理解，而且代码实现也比较简单。
3535

36+
**题目代码**
37+
3638
```java
3739
class Solution {
3840
public boolean isPalindrome(ListNode head) {
@@ -72,6 +74,10 @@ class Solution {
7274

7375
![翻转链表部分](https://cdn.jsdelivr.net/gh/tan45du/photobed@master/photo/翻转链表部分.1v2ncl72ligw.gif)
7476

77+
#### **题目代码**
78+
79+
Java Code：
80+
7581
```java
7682
class Solution {
7783
public boolean isPalindrome(ListNode head) {
@@ -129,3 +135,63 @@ class Solution {
129135
}
130136
```
131137

138+
C++ Code：
139+
140+
```cpp
141+
class Solution {
142+
public:
143+
bool isPalindrome(ListNode* head) {
144+
if (head == nullptr || head->next == nullptr) {
145+
return true;
146+
}
147+
//找到中间节点，也就是翻转的头节点,这个在昨天的题目中讲到
148+
//但是今天和昨天有一些不一样的地方就是，如果有两个中间节点返回第一个，昨天的题目是第二个
149+
ListNode * midenode = searchmidnode(head);
150+
//原地翻转链表，需要两个辅助指针。这个也是面试题目，大家可以做一下
151+
//这里我们用的是midnode->next需要注意，因为我们找到的是中点，但是我们翻转的是后半部分
152+
153+
ListNode * backhalf = reverse(midenode->next);
154+
//遍历两部分链表，判断值是否相等
155+
ListNode * p1 = head;
156+
ListNode * p2 = backhalf;
157+
while (p2 != nullptr) {
158+
if (p1->val != p2->val) {
159+
return false;
160+
}
161+
p1 = p1->next;
162+
p2 = p2->next;
163+
}
164+
// 还原链表并返回结果,这一步是需要注意的，我们不可以破坏初始结构，我们只是判断是否为回文，
165+
//当然如果没有这一步也是可以AC，但是面试的时候题目要求可能会有这一条。
166+
midenode->next = reverse(backhalf);
167+
return true;
168+
}
169+
//找到中间的部分
170+
ListNode * searchmidnode (ListNode * head) {
171+
ListNode * fast = new ListNode(-1);
172+
ListNode * slow = new ListNode(-1);
173+
fast = head;
174+
slow = head;
175+
//找到中点
176+
while (fast->next != nullptr && fast->next->next != nullptr) {
177+
fast = fast->next->next;
178+
slow = slow->next;
179+
}
180+
return slow;
181+
}
182+
//翻转链表
183+
ListNode * reverse (ListNode * slow) {
184+
ListNode * low = nullptr;
185+
ListNode * temp = nullptr;
186+
//翻转链表
187+
while (slow != nullptr) {
188+
temp = slow->next;
189+
slow->next = low;
190+
low = slow;
191+
slow = temp;
192+
}
193+
return low;
194+
}
195+
};
196+
```
197+

‎animation-simulation/链表篇/leetcode141环形链表.md

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -72,3 +72,24 @@ var hasCycle = function(head) {
7272
return false;
7373
};
7474
```
75+
76+
C++ Code:
77+
78+
```cpp
79+
class Solution {
80+
public:
81+
bool hasCycle(ListNode *head) {
82+
ListNode * fast = head;
83+
ListNode * low = head;
84+
while (fast != nullptr && fast->next != nullptr) {
85+
fast = fast->next->next;
86+
low = low->next;
87+
if (fast == low) {
88+
return true;
89+
}
90+
}
91+
return false;
92+
}
93+
};
94+
```
95+

‎animation-simulation/链表篇/leetcode142环形链表2.md

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -123,7 +123,9 @@ public class Solution {
123123

124124
![环形链表2](https://cdn.jsdelivr.net/gh/tan45du/photobed@master/photo/环形链表2.elwu1pw2lw0.gif)
125125

126+
**题目代码**
126127

128+
Java Code:
127129

128130
```java
129131
public class Solution {
@@ -153,3 +155,34 @@ public class Solution {
153155
}
154156
```
155157

158+
C++ Code:
159+
160+
```cpp
161+
class Solution {
162+
public:
163+
ListNode *detectCycle(ListNode *head) {
164+
//快慢指针
165+
ListNode * fast = head;
166+
ListNode * low = head;
167+
//设置循环条件
168+
while (fast != nullptr && fast->next != nullptr) {
169+
fast = fast->next->next;
170+
low = low->next;
171+
//相遇
172+
if (fast == low) {
173+
//设置一个新的指针，从头节点出发，慢指针速度为1，所以可以使用慢指针从相遇点出发
174+
ListNode * newnode = head;
175+
while (newnode != low) {
176+
low = low->next;
177+
newnode = newnode->next;
178+
}
179+
//在环入口相遇
180+
return low;
181+
}
182+
}
183+
return nullptr;
184+
185+
}
186+
};
187+
```
188+

‎animation-simulation/链表篇/leetcode147对链表进行插入排序.md

Lines changed: 41 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -82,6 +82,8 @@
8282

8383
**题目代码**
8484

85+
Java Code:
86+
8587
```java
8688
class Solution {
8789
public ListNode insertionSortList(ListNode head) {
@@ -121,7 +123,45 @@ class Solution {
121123
}
122124
```
123125

124-
126+
C++ Code:
127+
128+
```cpp
129+
class Solution {
130+
public:
131+
ListNode* insertionSortList(ListNode* head) {
132+
if (head == nullptr && head->next == nullptr) {
133+
return head;
134+
}
135+
//哑节点
136+
ListNode * dummyNode = new ListNode(-1);
137+
dummyNode->next = head;
138+
//pre负责指向新元素，last 负责指向新元素的前一元素
139+
//判断是否需要执行插入操作
140+
ListNode * pre = head->next;
141+
ListNode * last = head;
142+
ListNode * temphead = dummyNode;
143+
while (pre != nullptr) {
144+
//不需要插入到合适位置，则继续往下移动
145+
if (last->val <= pre->val) {
146+
pre = pre->next;
147+
last = last->next;
148+
continue;
149+
}
150+
//开始出发，查找新元素的合适位置
151+
temphead = dummyNode;
152+
while (temphead->next->val <= pre->val) {
153+
temphead = temphead->next;
154+
}
155+
//此时我们已经找到了合适位置，我们需要进行插入，大家可以画一画
156+
last->next = pre->next;
157+
pre->next = temphead->next;
158+
temphead->next = pre;
159+
pre = last->next;
160+
}
161+
return dummyNode->next;
162+
}
163+
};
164+
```
125165
126166
127167

‎animation-simulation/链表篇/leetcode206反转链表.md

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,10 @@ low = temp 即可。然后重复执行上诉操作直至最后，这样则完成
3333

3434
我会对每个关键点进行注释，大家可以参考动图理解。
3535

36+
37+
38+
**题目代码**
39+
3640
Java Code:
3741
```java
3842
class Solution {
@@ -81,8 +85,44 @@ var reverseList = function(head) {
8185
};
8286
```
8387

88+
C++代码
89+
90+
```cpp
91+
class Solution {
92+
public:
93+
ListNode* reverseList(ListNode* head) {
94+
//特殊情况
95+
if (head == nullptr || head->next == nullptr) {
96+
return head;
97+
}
98+
//反转
99+
return reverse(head);
100+
}
101+
ListNode * reverse (ListNode * head) {
102+
103+
ListNode * low = nullptr;
104+
ListNode * pro = head;
105+
while (pro != nullptr) {
106+
//代表橙色指针
107+
ListNode * temp = pro;
108+
//移动绿色指针
109+
pro = pro->next;
110+
//反转节点
111+
temp->next = low;
112+
//移动黄色指针
113+
low = temp;
114+
}
115+
return low;
116+
}
117+
};
118+
```
119+
84120
上面的迭代写法是不是搞懂啦，现在还有一种递归写法，不是特别容易理解，刚开始刷题的同学，可以只看迭代解法。
85121
122+
123+
124+
**题目代码**
125+
86126
Java Code:
87127
```java
88128
class Solution {
@@ -118,3 +158,26 @@ var reverseList = function(head) {
118158
};
119159
```
120160

161+
C++代码:
162+
163+
```cpp
164+
class Solution {
165+
public:
166+
ListNode * reverseList(ListNode * head) {
167+
//结束条件
168+
if (head == nullptr || head->next == nullptr) {
169+
return head;
170+
}
171+
//保存最后一个节点
172+
ListNode * pro = reverseList(head->next);
173+
//将节点进行反转。我们可以这样理解 4->next->next = 4;
174+
//4->next = 5；
175+
//则 5->next = 4 则实现了反转
176+
head->next->next = head;
177+
//防止循环
178+
head->next = nullptr;
179+
return pro;
180+
}
181+
};
182+
```
183+

‎animation-simulation/链表篇/leetcode328奇偶链表.md

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,8 @@
3636

3737
#### 题目代码
3838

39+
Java Code:
40+
3941
```java
4042
class Solution {
4143
public ListNode oddEvenList(ListNode head) {
@@ -60,3 +62,30 @@ class Solution {
6062
}
6163
```
6264

65+
C++ Code:
66+
67+
```cpp
68+
class Solution {
69+
public:
70+
ListNode* oddEvenList(ListNode* head) {
71+
if (head == nullptr || head->next == nullptr) {
72+
return head;
73+
}
74+
ListNode * odd = head;
75+
ListNode * even = head->next;
76+
ListNode * evenhead = even;
77+
78+
while (odd->next != nullptr && even->next != nullptr) {
79+
//将偶数位合在一起，奇数位合在一起
80+
odd->next = even->next;
81+
odd = odd->next;
82+
even->next = odd->next;
83+
even = even->next;
84+
}
85+
//链接
86+
odd->next = evenhead;
87+
return head;
88+
}
89+
};
90+
```
91+

‎animation-simulation/链表篇/leetcode82删除排序链表中的重复元素II.md

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -39,6 +39,10 @@
3939

4040
![删除重复节点2](https://cdn.jsdelivr.net/gh/tan45du/photobed@master/photo/删除重复节点2.3btmii5cgxa0.gif)
4141

42+
**题目代码**
43+
44+
Java Code:
45+
4246
```java
4347
class Solution {
4448
public ListNode deleteDuplicates(ListNode head) {
@@ -68,3 +72,35 @@ class Solution {
6872
}
6973
```
7074

75+
C++ Code:
76+
77+
```cpp
78+
class Solution {
79+
public:
80+
ListNode* deleteDuplicates(ListNode* head) {
81+
if(head == nullptr || head->next == nullptr){
82+
return head;
83+
}
84+
ListNode * pre = head;
85+
ListNode * low = new ListNode(0);
86+
low->next = pre;
87+
ListNode * ret = new ListNode(-1);
88+
ret = low;
89+
while(pre != nullptr && pre->next != nullptr) {
90+
if (pre->val == pre->next->val) {
91+
while (pre != nullptr && pre->next != nullptr && pre->val == pre->next->val) {
92+
pre = pre->next;
93+
}
94+
pre = pre->next;
95+
low->next = pre;
96+
}
97+
else{
98+
pre = pre->next;
99+
low = low->next;
100+
}
101+
}
102+
return ret->next;
103+
}
104+
};
105+
```
106+

0 commit comments

Comments
 (0)