LeetCode刷题（24）～回文链表

题目描述

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

  

 

  
1
  
2
 

示例 2:

输入: 1->2->2->1
输出: true

  

 

  
1
  
2
 

解答 By 海轰

提交代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public: bool isPalindrome(ListNode* head) { vector<int> a; while(head) {
 a.push_back(head->val);
 head=head->next; } int i=0; int j=a.size()-1; while(i<=j) { if(a[i]!=a[j]) return false; else { ++i; --j; } } return true; }
};

  

 

  
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
 

运行结果

思路

解答

• 寻找中间点+反转后半部分
• 递归

寻找中间点+反转后半部分

bool isPalindrome(ListNode* head) { if(head == nullptr || head->next == nullptr) return true; ListNode* mid = midNode(head); ListNode* rNode = reversalNode(mid->next); mid->next = rNode; ListNode* cur = head; ListNode* rightNode = mid->next; while(rightNode != nullptr) { if (rightNode->val != cur->val) return false; cur = cur->next; rightNode = rightNode->next; } return true; } // 快慢指针来找中间节点 巧妙！！！ ListNode* midNode(ListNode *head) { if (head == nullptr) return head; ListNode* fastNode = head; ListNode* slowNode = head; while(fastNode && fastNode->next != nullptr && fastNode->next->next != nullptr) { fastNode = fastNode->next->next; slowNode = slowNode->next; } return slowNode; } // 翻转链表 ListNode* reversalNode(ListNode* head) { ListNode* cur = head; ListNode* pre = nullptr; while(cur != nullptr) { ListNode* tempNextNode = cur->next; cur->next = pre; pre = cur; cur = tempNextNode; } return pre; }

  

 

  
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
 

快慢指针+同时反转前半部分【巧妙！！！】

bool isPalindrome(ListNode* head) { if(!head || !head->next) return 1; ListNode *fast = head, *slow = head; ListNode *p, *pre = NULL; while(fast && fast->next){ p = slow; slow = slow->next; //快慢遍历 fast = fast->next->next; p->next = pre;  //翻转 pre = p; } if(fast)  //奇数个节点时跳过中间节点 slow = slow->next; while(p){ //前半部分和后半部分比较 if(p->val != slow->val) return 0; p = p->next; slow = slow->next; } return 1; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

递归
暂无

参考资料

https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode/
https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-1zhan-2kuai-man-zhi-zhen-fan-zhu/

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/107870130