JAVA练习292- 回文链表

题目概览给你一个单链表的头节点head请你判断该链表是否为回文链表。如果是返回true否则返回false。示例 1输入head [1,2,2,1]输出true示例 2输入head [1,2]输出false提示链表中节点数目在范围[1, 10^5]内0 Node.val 9进阶你能否用O(n)时间复杂度和O(1)空间复杂度解决此题来源234. 回文链表 - 力扣LeetCode解题分析方法一栈利用栈先进后出的特性先遍历一遍将节点存进去然后出栈做比较。第一次遍历可以记录一下节点数出栈时只需要遍历节点数一半的节点即可。时间复杂度O(n)空间复杂度O(n)/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public boolean isPalindrome(ListNode head) { StackListNode stack new Stack(); ListNode temp head; int len 0; while(temp ! null) { stack.push(temp); temp temp.next; len; } len / 2; while(len 0) { if (head.val ! stack.pop().val) { return false; } head head.next; len--; } return true; } }方法二快慢指针定义两个指针 i 和 j 一起遍历i 遍历一个节点j 遍历两个节点那么当 j 的节点或下一个节点为空时i 所在节点一定是当前链表中心节点。因此只需要把中心节点后面的链表进行反转然后与头节点依次比较即可。时间复杂度O(n)空间复杂度O(1)class Solution { public boolean isPalindrome(ListNode head) { ListNode center head, end head; while(center ! null end ! null end.next ! null) { center center.next; end end.next.next; } ListNode reverseCenter null; while(center ! null) { ListNode temp center.next; center.next reverseCenter; reverseCenter center; center temp; } while (reverseCenter ! null) { if (reverseCenter.val ! head.val) { return false; } reverseCenter reverseCenter.next; head head.next; } return true; } }