C# 回文链表

234 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：
在这里插入图片描述

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

示例 2：
在这里插入图片描述

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

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

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

解决方案：

提供思路

1）最直观的方法是用数组存储链表中的每个结点的值，然后判断数组中的元素是否构成回文。遍历列表，将每个结点的值依次加入数组数字，此时数组中的元素顺序和链表的每个结点的值的顺序一致。

假设链表的结点数是大小，则数组数字的长度也是大小。数组数字中的元素构成回文，当且仅当对任意0≤我<大小都有数字[I]=数字[大小−1−我]。

2）为了将空间复杂度降低到O(1)，不能使用数组存储链表的结点值，而是需要将链表的一半反转，然后比较链表的前后两半是否相同。

为了将链表的一半反转，需要首先找到链表的中间结点。可以使用「876. 链表的中间结点」的快慢指针的做法，使用O(1)空间找到链表的中间结点，当链表的结点数是偶数时，得到的是链表的第二个中间结点。快慢指针遍历结束时，快指针快移动到链表的尾结点或者空结点，慢指针慢移动到链表的中间结点。

链表的前一半为慢前面的部分，不包含慢，链表的后一半则由链表结点数的奇偶性决定：

·当链表的结点数是奇数时，链表的后一半从慢。下一个开始，此时链表的中间结点既不属于前一半也不属于后一半，其余每个结点都属于前一半或者后一半；

·当链表的结点数是偶数时，链表的后一半从慢开始，此时链表的每个结点都属于前一半或者后一半。

确定链表的前一半和后一半之后，将链表的前一半反转，即反转慢前面的部分，反转的部分不包含慢。反转链表的做法可以使用「206. 反转链表」的迭代解法，使得空间复杂度为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;}
}