题解 | #13.判断一个链表是否为回文结构#

双指针、反转链表

将后半链表反转，在于前一半链表逐一比较

注意：

1.判断链表长度为奇数个还是偶数个！！！

2.奇数个链表时slow会成为正中间，将slow后移一个，确保slow的长度<=fast的长度

3.注意比较的条件是slow!=null而不是fast!=null

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param head ListNode类 the head
 * @return bool布尔型
 */
 function isPail( head ) {
  let fast = head,slow = head;
  
  while(fast!=null && fast.next!=null){
    fast = fast.next.next;
    slow = slow.next;
  }//此时slow是链表中点
  
  if(fast!=null){//长度为奇数个
    slow = slow.next;
  }
  fast = head;
  //反转后半链表
  let pre = null, slowHead = slow, temp = null;
  while(slowHead!=null){
    temp = slowHead.next;
    slowHead.next = pre;
    pre = slowHead;
    slowHead = temp;
  }
  
  slow = pre;//slow为反转链表后的头节点
  
  while(slow!=null){//必须是slow 如果是fast会出现错误
    if(fast.val != slow.val)
      return false;
    fast = fast.next;
    slow = slow.next;
  }
  return true;
}
module.exports = {
    isPail : isPail
};