https://leetcode.com/problems/palindrome-linked-list/
https://www.geeksforgeeks.org/function-to-check-if-a-singly-linked-list-is-palindrome/
Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2 Output: false
Example 2:
Input: 1->2->2->1 Output: true
Follow up:
Could you do it in O(n) time and O(1) space?
判断是否是回文
结，连结，终结
节，关节
可以这样做简单的区分
节点被认为是一个实体，有处理能力，比如说网络上的一台计算机；结点则只是一个交叉点，像“结绳记事”，打个结，做个标记，仅此而已。一般算法
中点都是结点。
那么复杂网络理论中所谈到的点应该是“节点”了。
解题思路，首先需要找到链表的中间结点。
使用双指针，刚开始都指向head，然后指针fast,每次移动2个。slow每次移动1个。
1.链表中奇数个元素，比如5个。
1->2->3->4->5->null
fast slow
1 1
3 2
5 3 因为fast.next是null,所以不会进行下一次循环。 奇数个元素的时候fast不为null，并且fast.next为null。slow所在的位置是中间位置。
2.链表中偶数个元素，比如6个
1->2->3->4->5->6-->null
fast slow
1 1
3 2
5 3 因为fast.next是6，不为null，所以还会再循环一次才结束。
null 4 fast为null，slow_prev指向3，slow指向4. 偶数个元素的时候，fast为null。并且slow所在的位置，是下半段456的第一个结点。
根据中间结点，把链表分为两段。
while循环来移动指针，当fast.next不为null，并且fast.next.next不为null的时候进行循环。
奇数的时候(slow所在的位置是中间位置)
需要拿到slow的前一个结点slow_prev，然后设置slow_prev.next为null。这样从head 到slow_prev就是上半段。
拿到slow.next作为下半段的head,然后遍历到next为null的结点，就是下半段了。
偶数的时候(slow所在的位置，是下半段的第一个结点)
设置slow_prev.next为null，从head到slow_prev就是上半段。
slow是下半段的head,然后遍历到next为null的结点，就是下半段了。
单链表反转的代码，是直接从https://www.cnblogs.com/chucklu/p/10417793.html这个题目的官方solution里拿的。
需要说明的是，之前的分析，漏掉了单个结点也是回文。单结点的时候slow.next无法作为第二个的head。
public bool IsPalindrome(ListNode head) { if (head?.next == null) { return true; } var slow = head; var fast = head; ListNode firstHead = head; ListNode secondHead; ListNode slowPrev = null; // Get the middle of the list. // Move slow by 1 and fast by 2 // slow will have the middle mode while (fast?.next != null) { fast = fast.next.next; //We need previous of the slow_ptr for linked lists with odd elements slowPrev = slow; slow = slow.next; } if (slowPrev != null) { slowPrev.next = null; } if (fast != null) { //not null for odd elements secondHead = slow.next; } else { secondHead = slow; } secondHead = ReverseList(secondHead); bool flag = true; while (firstHead != null && secondHead != null) { if (firstHead.val != secondHead.val) { flag = false; break; } else { firstHead = firstHead.next; secondHead = secondHead.next; } } if (firstHead != null || secondHead != null) { flag = false; } return flag; } public ListNode ReverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev; }