Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
判断一个链表是否为回文串
思路:1.找到中间点,2.反转后半部分链表,3.判断前半部分与后半部分是否相同
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode ReverseList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode nextNode = head.next;
ListNode newHead = ReverseList(nextNode);
nextNode.next = head;
head.next = null;
return newHead;
}
public ListNode FindMid(ListNode head) {
ListNode fast = head;
ListNode slow = head;
int num = 1;
while (fast != null) {
num++;
if (fast.next != null) {
fast = fast.next.next;
} else {
break;
}
slow = slow.next;
}
return slow;
}
public bool IsPalindrome(ListNode head) {
if (head == null) {
return true;
}
ListNode midNode = FindMid(head);
ListNode newMid = ReverseList(midNode);
ListNode font = head;
ListNode back = newMid;
while (back != null) {
if (font.val != back.val) {
return false;
}
font = font.next;
back = back.next;
}
return true;
}
}