234 回文鏈表

給你一個(gè)單鏈表的頭節(jié)點(diǎn) head ，請你判斷該鏈表是否為回文鏈表。如果是，返回 true ；否則，返回 false 。

示例 1：

輸入：head = [1,2,2,1]
輸出：true

示例 2：

輸入：head = [1,2]
輸出：false

提示：

鏈表中節(jié)點(diǎn)數(shù)目在范圍[1, 105] 內(nèi)
0 <= Node.val <= 9

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/palindrome-linked-list

解決方案：

提供思路

1） 最直觀的方法是用數(shù)組存儲鏈表中的每個(gè)結(jié)點(diǎn)的值，然后判斷數(shù)組中的元素是否構(gòu)成回文。遍歷列表，將每個(gè)結(jié)點(diǎn)的值依次加入數(shù)組數(shù)字，此時(shí)數(shù)組中的元素順序和鏈表的每個(gè)結(jié)點(diǎn)的值的順序一致。

假設(shè)鏈表的結(jié)點(diǎn)數(shù)是大小，則數(shù)組數(shù)字的長度也是大小。數(shù)組數(shù)字中的元素構(gòu)成回文，當(dāng)且僅當(dāng)對任意0≤我<大小都有數(shù)字[I]=數(shù)字[大小?1?我]。

2）為了將空間復(fù)雜度降低到O(1)，不能使用數(shù)組存儲鏈表的結(jié)點(diǎn)值，而是需要將鏈表的一半反轉(zhuǎn)，然后比較鏈表的前后兩半是否相同。

為了將鏈表的一半反轉(zhuǎn)，需要首先找到鏈表的中間結(jié)點(diǎn)。可以使用「876. 鏈表的中間結(jié)點(diǎn)」的快慢指針的做法，使用O(1)空間找到鏈表的中間結(jié)點(diǎn)，當(dāng)鏈表的結(jié)點(diǎn)數(shù)是偶數(shù)時(shí)，得到的是鏈表的第二個(gè)中間結(jié)點(diǎn)。快慢指針遍歷結(jié)束時(shí)，快指針快移動到鏈表的尾結(jié)點(diǎn)或者空結(jié)點(diǎn)，慢指針慢移動到鏈表的中間結(jié)點(diǎn)。

鏈表的前一半為慢前面的部分，不包含慢，鏈表的后一半則由鏈表結(jié)點(diǎn)數(shù)的奇偶性決定：

·當(dāng)鏈表的結(jié)點(diǎn)數(shù)是奇數(shù)時(shí)，鏈表的后一半從慢。下一個(gè)開始，此時(shí)鏈表的中間結(jié)點(diǎn)既不屬于前一半也不屬于后一半，其余每個(gè)結(jié)點(diǎn)都屬于前一半或者后一半；

·當(dāng)鏈表的結(jié)點(diǎn)數(shù)是偶數(shù)時(shí)，鏈表的后一半從慢開始，此時(shí)鏈表的每個(gè)結(jié)點(diǎn)都屬于前一半或者后一半。

確定鏈表的前一半和后一半之后，將鏈表的前一半反轉(zhuǎn)，即反轉(zhuǎn)慢前面的部分，反轉(zhuǎn)的部分不包含慢。反轉(zhuǎn)鏈表的做法可以使用「206. 反轉(zhuǎn)鏈表」的迭代解法，使得空間復(fù)雜度為O(1)。

上代碼：

//1
public class Solution
{public bool IsPalindrome(ListNode head){IList<int> nums = new List<int>();ListNode node = head;while (node != null){nums.Add(node.val);node = node.next;}int size = nums.Count;for (int i = (size - 1) / 2; i >= 0; i--){int j = size - 1 - i;if (nums[i] != nums[j]){return false;}}return true;}
}//2
public class Solution
{public bool IsPalindrome(ListNode head){ListNode fast = head, slow = head;while (fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}bool odd = fast != null;ListNode firstHalfEnd = slow;ListNode secondHalfStart = odd ? slow.next : slow;ListNode node1 = ReverseFirstHalf(head, firstHalfEnd);ListNode node2 = secondHalfStart;while (node1 != null){if (node1.val != node2.val){return false;}node1 = node1.next;node2 = node2.next;}return true;}public ListNode ReverseFirstHalf(ListNode head, ListNode firstHalfEnd){ListNode prev = null, curr = head;while (curr != firstHalfEnd){ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}
}

以上是碰到的第二百三十四題，后續(xù)持續(xù)更新。感覺對你有幫助的小伙伴可以幫忙點(diǎn)個(gè)贊噢！