【百日算法计划】：每日一题，见证成长（013）
题目
回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
输入：head = [1,2,2,1]
输出：true
思路
- 找到中间节点
- 反转后半部分链表
- 前后链表顺序比对
public boolean isPalindrome2(ListNode head) {
if (head == null || head.next == null) return true;
ListNode p = head;
ListNode middleNode = findMiddleNode(p);
ListNode q = reverseNode(middleNode.next); //因为要区分奇偶 所以传入中间节点的后一个节点
while (q != null){
if (p.val != q.val){
return false;
}
p = p.next;
q = q.next;
}
return true;
}
//寻找中间节点
public ListNode findMiddleNode(ListNode head){
ListNode p1 = head;
ListNode p2 = head;
while(p1 != null && p1.next != null){
p1 = p1.next.next;
p2 = p2.next;
}
return p2;
}
//反转后半部分链表
public ListNode reverseNode(ListNode head){
ListNode p = head;
ListNode pre = null;
while(p != null){
ListNode tmp = p.next;
p.next = pre;
pre = p;
p = tmp;
}
return pre;
}