一道新的面試題回文鏈表你會么？
作者：程序員Carl
在我們的生活中經常會碰到這種回文的結構，回文就是反轉以后和以前一樣的就是回文結構，例如 1->2->3->2->1，我們將它反轉之后還是與原鏈表一樣，我們就稱這種鏈表結構為回文結構。
新題來咯，回文鏈表
回文鏈表
力扣題目鏈接：https://leetcode-cn.com/problems/palindrome-linked-list/
請判斷一個鏈表是否為回文鏈表。
示例 1:
- 輸入: 1->2
- 輸出: false
示例 2:
- 輸入: 1->2->2->1
- 輸出: true
思路
數組模擬
最直接的想法，就是把鏈表裝成數組，然后再判斷是否回文。
代碼也比較簡單。如下：
- class Solution {
- public:
- bool isPalindrome(ListNode* head) {
- vector<int> vec;
- ListNode* cur = head;
- while (cur) {
- vec.push_back(cur->val);
- cur = cur->next;
- }
- // 比較數組回文
- for (int i = 0, j = vec.size() - 1; i < j; i++, j--) {
- if (vec[i] != vec[j]) return false;
- }
- return true;
- }
- };
上面代碼可以在優化，就是先求出鏈表長度，然后給定vector的初始長度，這樣避免vector每次添加節點重新開辟空間
- class Solution {
- public:
- bool isPalindrome(ListNode* head) {
- ListNode* cur = head;
- int length = 0;
- while (cur) {
- length++;
- cur = cur->next;
- }
- vector<int> vec(length, 0); // 給定vector的初始長度，這樣避免vector每次添加節點重新開辟空間
- cur = head;
- int index = 0;
- while (cur) {
- vec[index++] = cur->val;
- cur = cur->next;
- }
- // 比較數組回文
- for (int i = 0, j = vec.size() - 1; i < j; i++, j--) {
- if (vec[i] != vec[j]) return false;
- }
- return true;
- }
- };
反轉后半部分鏈表
分為如下幾步：
- 用快慢指針，快指針有兩步，慢指針走一步，快指針遇到終止位置時，慢指針就在鏈表中間位置
- 同時用pre記錄慢指針指向節點的前一個節點，用來分割鏈表
- 將鏈表分為前后均等兩部分，如果鏈表長度是奇數，那么后半部分多一個節點
- 將后半部分反轉 ，得cur2，前半部分為cur1
- 按照cur1的長度，一次比較cur1和cur2的節點數值
如圖所示：
代碼如下：
- class Solution {
- public:
- bool isPalindrome(ListNode* head) {
- if (head == nullptr || head->next == nullptr) return true;
- ListNode* slow = head; // 慢指針，找到鏈表中間分位置，作為分割
- ListNode* fast = head;
- ListNode* pre = head; // 記錄慢指針的前一個節點，用來分割鏈表
- while (fast && fast->next) {
- pre = slow;
- slow = slow->next;
- fast = fast->next->next;
- }
- pre->next = nullptr; // 分割鏈表
- ListNode* cur1 = head; // 前半部分
- ListNode* cur2 = reverseList(slow); // 反轉后半部分，總鏈表長度如果是奇數，cur2比cur1多一個節點
- // 開始兩個鏈表的比較
- while (cur1) {
- if (cur1->val != cur2->val) return false;
- cur1 = cur1->next;
- cur2 = cur2->next;
- }
- return true;
- }
- // 反轉鏈表
- ListNode* reverseList(ListNode* head) {
- ListNode* temp; // 保存cur的下一個節點
- ListNode* cur = head;
- ListNode* pre = nullptr;
- while(cur) {
- temp = cur->next; // 保存一下 cur的下一個節點，因為接下來要改變cur->next
- cur->next = pre; // 翻轉操作
- // 更新pre 和 cur指針
- pre = cur;
- cur = temp;
- }
- return pre;
- }
- };
其他語言版本
Java
- // 方法一，使用數組
- class Solution {
- public boolean isPalindrome(ListNode head) {
- int len = 0;
- // 統計鏈表長度
- ListNode cur = head;
- while (cur != null) {
- len++;
- cur = cur.next;
- }
- cur = head;
- int[] res = new int[len];
- // 將元素加到數組之中
- for (int i = 0; i < res.length; i++){
- res[i] = cur.val;
- cur = cur.next;
- }
- // 比較回文
- for (int i = 0, j = len - 1; i < j; i++, j--){
- if (res[i] != res[j]){
- return false;
- }
- }
- return true;
- }
- }
- // 方法二，快慢指針
- class Solution {
- public boolean isPalindrome(ListNode head) {
- // 如果為空或者僅有一個節點，返回true
- if (head == null && head.next == null) return true;
- ListNode slow = head;
- ListNode fast = head;
- ListNode pre = head;
- while (fast != null && fast.next != null){
- pre = slow; // 記錄slow的前一個結點
- slow = slow.next;
- fast = fast.next.next;
- }
- pre.next = null; // 分割兩個鏈表
- // 前半部分
- ListNode cur1 = head;
- // 后半部分。這里使用了反轉鏈表
- ListNode cur2 = reverseList(slow);
- while (cur1 != null){
- if (cur1.val != cur2.val) return false;
- // 注意要移動兩個結點
- cur1 = cur1.next;
- cur2 = cur2.next;
- }
- return true;
- }
- ListNode reverseList(ListNode head){
- // 反轉鏈表
- ListNode tmp = null;
- ListNode pre = null;
- while (head != null){
- tmp = head.next;
- head.next = pre;
- pre = head;
- head = tmp;
- }
- return pre;
- }
- }
Python
- #數組模擬
- class Solution:
- def isPalindrome(self, head: ListNode) -> bool:
- length = 0
- tmp = head
- while tmp: #求鏈表長度
- length += 1
- tmp = tmp.next
- result = [0] * length
- tmp = head
- index = 0
- while tmp: #鏈表元素加入數組
- result[index] = tmp.val
- index += 1
- tmp = tmp.next
- i, j = 0, length - 1
- while i < j: # 判斷回文
- if result[i] != result[j]:
- return False
- i += 1
- j -= 1
- return True
- #反轉后半部分鏈表
- class Solution:
- def isPalindrome(self, head: ListNode) -> bool:
- if head == None or head.next == None:
- return True
- slow, fast = head, head
- while fast and fast.next:
- pre = slow
- slow = slow.next
- fast = fast.next.next
- pre.next = None # 分割鏈表
- cur1 = head # 前半部分
- cur2 = self.reverseList(slow) # 反轉后半部分，總鏈表長度如果是奇數，cur2比cur1多一個節點
- while cur1:
- if cur1.val != cur2.val:
- return False
- cur1 = cur1.next
- cur2 = cur2.next
- return True
- def reverseList(self, head: ListNode) -> ListNode:
- cur = head
- pre = None
- while(cur!=None):
- temp = cur.next # 保存一下cur的下一個節點
- cur.next = pre # 反轉
- pre = cur
- cur = temp
- return pre
責任編輯：姜華
來源：
代碼隨想錄
