郑州网站建设汉狮,产品单页营销型网站模板下载,网站短片怎么做,wordpress微信付款题目描述
请判断一个链表是否为回文链表。
示例 1:
输入: 1-2
输出: false示例 2:
输入: 1-2-2-1
输出: true进阶#xff1a; 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题#xff1f;
解题
思路1#xff1a;直接利用List的顺序存储性#x…题目描述
请判断一个链表是否为回文链表。
示例 1:
输入: 1-2
输出: false示例 2:
输入: 1-2-2-1
输出: true进阶 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题
解题
思路1直接利用List的顺序存储性解题
/*** 思路1数组存储法* 时间复杂度O(n),空间复杂度O(n)* param head* return*/public boolean isPalindrome1(ListNode head) {ListInteger list new ArrayListInteger();while(head!null) {list.add(head.val);headhead.next;}int size list.size();for(int i0;isize/2;i) {if(list.get(i).intValue() ! list.get(size-1-i).intValue() ) {return false;}}return true;}**思路2**利用栈的入栈、出栈改变集合顺序原理
public boolean isPalindrome(ListNode head) {StackInteger s new Stack();ListNode cur head;//将整个链表入栈之后出栈的顺序其实就是链表的逆序while(cur ! null){s.push(cur.val);cur cur.next;}cur head;while(!s.isEmpty()){if(s.pop() ! cur.val){return false;}cur cur.next;}return true;}思路3
/*** 思路3* 1.快慢指针找到中间节点* 2.反转后半段链表* 3.顺序比较链表前后半段都相等则为回文* 时间复杂度O(n)空间复杂度O(1)* param head* return*/public boolean isPalindrome(ListNode head) {if(head null) {return true;}ListNode slow head, fasthead, midnull;while(fast!null fast.next!null) {slow slow.next;fast fast.next.next;}mid slow;ListNode cur mid, next mid.next, nNextnull;//链表从中间截断cur.next null;while (next ! null) {nNext next.next;next.next cur;cur next;next nNext;}while(cur ! null) {if(head.val ! cur.val) {return false;}head head.next;cur cur.next;}return true;}
