1-
2-
31> 如果阅读时，发现错误，或者动画不可以显示的问题可以添加我微信好友 ** [ tan45du_one] ( https://raw.githubusercontent.com/tan45du/tan45du.github.io/master/个人微信.15egrcgqd94w.jpg ) ** ，备注 github + 题目 + 问题 向我反馈
42>
53> 感谢支持，该仓库会一直维护，希望对各位有一丢丢帮助。
3533
3634** 题目代码**
3735
36+ Java Code:
37+
3838``` java
3939class Solution {
4040 public boolean isPalindrome (ListNode head ) {
@@ -46,7 +46,7 @@ class Solution {
4646 arr. add(copynode. val);
4747 copynode = copynode. next;
4848 }
49- // 双指针遍历数组
49+ // 双指针遍历数组
5050 int back = 0 ;
5151 int pro = arr. size() - 1 ;
5252 while (back < pro) {
@@ -61,12 +61,93 @@ class Solution {
6161 return true ;
6262 }
6363}
64+ ```
65+
66+ C++ Code:
67+
68+ ``` cpp
69+ class Solution {
70+ public:
71+ bool isPalindrome(ListNode* head) {
72+ //这里需要用动态数组，因为我们不知道链表的长度
73+ vector<int > arr;
74+ ListNode* copynode = head;
75+ //将链表的值复制到数组中
76+ while (copynode) {
77+ arr.push_back(copynode->val);
78+ copynode = copynode->next;
79+ }
80+ //双指针遍历数组
81+ int back = 0;
82+ int pro = arr.size() - 1;
83+ while (back < pro) {
84+ //判断两个指针的值是否相等
85+ if (arr[ back] != arr[ pro] ) {
86+ return false;
87+ }
88+ //移动指针
89+ back++;
90+ pro--;
91+ }
92+ return true;
93+ }
94+ };
95+ ```
96+
97+ JS Code:
98+
99+ ```js
100+ var isPalindrome = function(head) {
101+ let arr = [];
102+ let copynode = head;
103+ //将链表的值复制到数组中
104+ while (copynode) {
105+ arr.push(copynode.val)
106+ copynode = copynode.next
107+ }
108+ //双指针遍历数组
109+ let back = 0;
110+ let pro = arr.length - 1;
111+ while (back < pro) {
112+ //判断两个指针的值是否相等
113+ if (arr[back] !== arr[pro]) {
114+ return false
115+ }
116+ //移动指针
117+ back += 1
118+ pro -= 1
119+ }
120+ return true
121+ };
122+ ```
123+
124+ Python Code:
64125
126+ ``` python
127+ class Solution :
128+ def isPalindrome (self head : ListNode) -> bool :
129+ arr = []
130+ copynode = head
131+ # 将链表的值复制到数组中
132+ while copynode is not None :
133+ arr.append(copynode.val)
134+ copynode = copynode.next
135+ # 双指针遍历数组
136+ back = 0
137+ pro = len (arr) - 1
138+ while back < pro:
139+ # 判断两个指针的值是否相等
140+ if arr[back] != arr[pro]:
141+ return False
142+ # 移动指针
143+ back += 1
144+ pro -= 1
145+ return True
65146```
66147
67148这个方法可以直接通过，但是这个方法需要辅助数组，那我们还有其他更好的方法吗？
68149
69- 双指针翻转链表法
150+ ** 双指针翻转链表法**
70151
71152在上个题目中我们知道了如何找到链表的中间节点，那我们可以在找到中间节点之后，对后半部分进行翻转，翻转之后，重新遍历前半部分和后半部分进行判断是否为回文。
72153
@@ -82,37 +163,35 @@ Java Code：
82163class Solution {
83164 public boolean isPalindrome (ListNode head ) {
84165 if (head== null || head. next== null ) {
85- return true ;
166+ return true ;
86167 }
87168 // 找到中间节点，也就是翻转的头节点,这个在昨天的题目中讲到
88169 // 但是今天和昨天有一些不一样的地方就是，如果有两个中间节点返回第一个，昨天的题目是第二个
89- ListNode midenode = searchmidnode(head);
170+ ListNode midnode = searchmidnode(head);
90171 // 原地翻转链表，需要两个辅助指针。这个也是面试题目，大家可以做一下
91172 // 这里我们用的是midnode.next需要注意，因为我们找到的是中点，但是我们翻转的是后半部分
92-
93- ListNode backhalf = reverse(midenode. next);
173+ ListNode backhalf = reverse(midnode. next);
94174 // 遍历两部分链表，判断值是否相等
95175 ListNode p1 = head;
96176 ListNode p2 = backhalf;
97177 while (p2 != null ) {
98178 if (p1. val != p2. val) {
99- return false ;
179+ // 若要还原，记得这里也要reverse
180+ midnode. next = reverse(backhalf);
181+ return false ;
100182 }
101183 p1 = p1. next;
102184 p2 = p2. next;
103185 }
104- // 还原链表并返回结果, 这一步是需要注意的，我们不可以破坏初始结构，我们只是判断是否为回文，
186+ // 还原链表并返回结果， 这一步是需要注意的，我们不可以破坏初始结构，我们只是判断是否为回文，
105187 // 当然如果没有这一步也是可以AC，但是面试的时候题目要求可能会有这一条。
106- midenode . next = reverse(backhalf);
188+ midnode . next = reverse(backhalf);
107189 return true ;
108190 }
109- // 找到中间的部分
110- public ListNode searchmidnode (ListNode head ) {
111- ListNode fast = new ListNode (- 1 );
112- ListNode slow = new ListNode (- 1 );
113- fast = head;
114- slow = head;
115- // 找到中点
191+ // 找到中点
192+ public ListNode searchmidnode (ListNode head ) {
193+ ListNode fast = head;
194+ ListNode slow = head;
116195 while (fast. next != null && fast. next. next != null ) {
117196 fast = fast. next. next;
118197 slow = slow. next;
@@ -123,12 +202,11 @@ class Solution {
123202 public ListNode reverse (ListNode slow ) {
124203 ListNode low = null ;
125204 ListNode temp = null ;
126- // 翻转链表
127205 while (slow != null ) {
128- temp = slow. next;
129- slow. next = low;
130- low = slow;
131- slow = temp;
206+ temp = slow. next;
207+ slow. next = low;
208+ low = slow;
209+ slow = temp;
132210 }
133211 return low;
134212 }
@@ -144,35 +222,33 @@ public:
144222 if (head == nullptr || head->next == nullptr) {
145223 return true;
146224 }
147- //找到中间节点，也就是翻转的头节点, 这个在昨天的题目中讲到
225+ //找到中间节点，也就是翻转的头节点， 这个在昨天的题目中讲到
148226 //但是今天和昨天有一些不一样的地方就是，如果有两个中间节点返回第一个，昨天的题目是第二个
149- ListNode * midenode = searchmidnode(head);
227+ ListNode * midnode = searchmidnode(head);
150228 //原地翻转链表，需要两个辅助指针。这个也是面试题目，大家可以做一下
151229 //这里我们用的是midnode->next需要注意，因为我们找到的是中点，但是我们翻转的是后半部分
152-
153- ListNode * backhalf = reverse(midenode->next);
230+ ListNode * backhalf = reverse(midnode->next);
154231 //遍历两部分链表，判断值是否相等
155232 ListNode * p1 = head;
156233 ListNode * p2 = backhalf;
157234 while (p2 != nullptr) {
158235 if (p1->val != p2->val) {
159- return false;
236+ //若要还原，记得这里也要reverse
237+ midnode->next = reverse(backhalf);
238+ return false;
160239 }
161240 p1 = p1->next;
162241 p2 = p2->next;
163242 }
164- // 还原链表并返回结果, 这一步是需要注意的，我们不可以破坏初始结构，我们只是判断是否为回文，
243+ //还原链表并返回结果， 这一步是需要注意的，我们不可以破坏初始结构，我们只是判断是否为回文，
165244 //当然如果没有这一步也是可以AC，但是面试的时候题目要求可能会有这一条。
166- midenode ->next = reverse(backhalf);
245+ midnode ->next = reverse(backhalf);
167246 return true;
168247 }
169248 //找到中间的部分
170- ListNode * searchmidnode (ListNode * head) {
171- ListNode * fast = new ListNode(-1);
172- ListNode * slow = new ListNode(-1);
173- fast = head;
174- slow = head;
175- //找到中点
249+ ListNode * searchmidnode (ListNode * head) {
250+ ListNode * fast = head;
251+ ListNode * slow = head;
176252 while (fast->next != nullptr && fast->next->next != nullptr) {
177253 fast = fast->next->next;
178254 slow = slow->next;
@@ -183,15 +259,119 @@ public:
183259 ListNode * reverse (ListNode * slow) {
184260 ListNode * low = nullptr;
185261 ListNode * temp = nullptr;
186- //翻转链表
187262 while (slow != nullptr) {
188- temp = slow->next;
189- slow->next = low;
190- low = slow;
191- slow = temp;
263+ temp = slow->next;
264+ slow->next = low;
265+ low = slow;
266+ slow = temp;
192267 }
193268 return low;
194269 }
195270};
196271```
197272
273+ JS Code:
274+
275+ ```javascript
276+ var isPalindrome = function(head) {
277+ if (head === null || head.next === null) {
278+ return true;
279+ }
280+ //找到中间节点，也就是翻转的头节点，这个在昨天的题目中讲到
281+ //但是今天和昨天有一些不一样的地方就是，如果有两个中间节点返回第一个，昨天的题目是第二个
282+ let midnode = searchmidnode(head);
283+ //原地翻转链表，需要两个辅助指针。这个也是面试题目，大家可以做一下
284+ //这里我们用的是midnode.next需要注意，因为我们找到的是中点，但是我们翻转的是后半部分
285+ let backhalf = reverse(midnode.next);
286+ //遍历两部分链表，判断值是否相等
287+ let p1 = head;
288+ let p2 = backhalf;
289+ while (p2 != null) {
290+ if (p1.val != p2.val) {
291+ //若要还原，记得这里也要reverse
292+ midnode.next = reverse(backhalf);
293+ return false;
294+ }
295+ p1 = p1.next;
296+ p2 = p2.next;
297+ }
298+ //还原链表并返回结果，这一步是需要注意的，我们不可以破坏初始结构，我们只是判断是否为回文，
299+ //当然如果没有这一步也是可以AC，但是面试的时候题目要求可能会有这一条。
300+ midnode.next = reverse(backhalf);
301+ return true;
302+ };
303+
304+ //找到中点
305+ var searchmidnode = function(head) {
306+ let fast = head;
307+ let slow = head;
308+ while (fast.next != null && fast.next.next != null) {
309+ fast = fast.next.next;
310+ slow = slow.next;
311+ }
312+ return slow;
313+ };
314+
315+ //翻转链表
316+ var reverse = function(slow) {
317+ let low = null;
318+ let temp = null;
319+ while (slow != null) {
320+ temp = slow.next;
321+ slow.next = low;
322+ low = slow;
323+ slow = temp;
324+ }
325+ return low;
326+ };
327+ ```
328+
329+ Python Code:
330+
331+ ``` python
332+ class Solution :
333+ def isPalindrome (self head : ListNode) -> bool :
334+ if head is None or head.next is None :
335+ return True
336+ # 找到中间节点，也就是翻转的头节点，这个在昨天的题目中讲到
337+ # 但是今天和昨天有一些不一样的地方就是，如果有两个中间节点返回第一个，昨天的题目是第二个
338+ midnode = self .searchmidnode(head)
339+ # 原地翻转链表，需要两个辅助指针。这个也是面试题目，大家可以做一下
340+ # 这里我们用的是midnode.next需要注意，因为我们找到的是中点，但是我们翻转的是后半部分
341+ backhalf = self .reverse(midnode.next)
342+ # 遍历两部分链表，判断值是否相等
343+ p1 = head
344+ p2 = backhalf
345+ while p2 is not None :
346+ if p1.val != p2.val:
347+ # 若要还原，记得这里也要reverse
348+ midnode.next = self .reverse(backhalf)
349+ return False
350+ p1 = p1.next
351+ p2 = p2.next
352+ # 还原链表并返回结果，这一步是需要注意的，我们不可以破坏初始结构，我们只是判断是否为回文，
353+ # 当然如果没有这一步也是可以AC，但是面试的时候题目要求可能会有这一条。
354+ midnode.next = self .reverse(backhalf)
355+ return True
356+
357+ # 找到中点
358+ def searchmidnode (self head ):
359+ fast = head
360+ slow = head
361+ while fast.next is not None and fast.next.next is not None :
362+ fast = fast.next.next
363+ slow = slow.next
364+ return slow
365+
366+ # 翻转链表
367+ def reverse (self slow ):
368+ low = None
369+ temp = None
370+ while slow is not None :
371+ temp = slow.next
372+ slow.next = low
373+ low = slow
374+ slow = temp
375+ return low
376+ ```
377+
0 commit comments