Leetcode hot100 回文链表【简单】

法一放数组里双指针直觉是跟“括号”那种题一样用一个栈遍历完链表后如果栈空则是回文。但是没考虑奇数个的情况比如 1 2 3 2 1。所以这种方法是行不通的。那就只能双指针一个从头遍历一个从尾遍历。但是仔细一想尾指针没法往前遍历。那就先把数拷贝到数组里偷看了官方题解再用双指针。链表题就是要画图。然后画图考虑奇数个和偶数个不同的停下方式。发现是一样的。无论是“1 2 2 1”还是奇数个“1 2 3 2 1”while循环里停下来的判断方式都是一样的fronttail的时候停下也就是while(fronttail)的时候继续循环。这是这个思路唯一的小难点。/** * 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) { //特殊情况处理 if(head.nextnull) return true; if(head.next.nextnull) return head.valhead.next.val; //1.数出来结点个数 int size0; ListNode counthead; while(count!null){ size; countcount.next; } //2.放到数组里 int[] nums new int[size]; counthead; int i0; while(count!null){ nums[i]count.val; i; countcount.next; } //3.判断回文 int front0; int tailsize-1; while(fronttail){ //这个题唯一的小难点就是在于fronttail if(nums[front]nums[tail]){ front; tail--; }else return false; } //如果正常退出的话就是回文 return true; } }时间复杂度O(3n)空间复杂度O(n)法二快慢指针找中点反转后半部分这是个简单题没必要这么麻烦如果进阶问你能够找到一个空间复杂度为O(1)的解法就可以这样做。但是没有进阶的要求的话你自己不要这样做因为考虑的细节太多了首先快慢指针找中点先画图分成奇数个和偶数个发现又可以用一样的代码。奇数个的时候假如节点编号是[1,2,3,4,5]slow慢指针刚好在中间[3]停下。假如节点编号是[1,2,3,4,5]那我们就反转slow.next作为头结点的后半部分链表也就是[4,5]去跟[1,2]比较。偶数个的时候假如节点编号是[1,2,3,4,5,6]slow慢支怎在[3]停下同样我们也反转slow.next作为头结点的后半部分链表也就是[4,5,6]跟[1,2,3]比较。如此时间复杂度依然是大概O(3n)但是空间复杂度为O(1)。给我背过快慢指针的写法/** * 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) { //特殊情况处理 if(head.nextnull) return true; if(head.next.nextnull) return head.valhead.next.val; //1.快慢指针找中点 ListNode slowhead; ListNode fasthead; while(fast.next!null fast.next.next!null){ fastfast.next.next; slowslow.next; } //退出while循环的时候slow.next后半部分链表的头结点 //2.反转链表 ListNode newHead reverse(slow.next); //3.同时比较两个链表 while(newHead!nullhead.valnewHead.val){ headhead.next; newHeadnewHead.next; } return newHeadnull; } private ListNode reverse(ListNode head){ //特殊情况 if(headnull) return head; if(head.nextnull) return head; //初始化刨除了特殊情况后肯定至少有两个结点 ListNode prehead; ListNode nowhead.next; ListNode nextNodehead.next.next; pre.nextnull; //别忘了这里不然成环了 while(true){ now.nextpre; prenow; nownextNode; if(now!null) nextNodenextNode.next; else break; } return pre; } }