网站做扫一扫app运营推广策划方案

题目

回文链表

给你一个单链表的头节点 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;
}