广州建设六马路小学网站,崇义网站建设,西宁制作网站需要多少钱,企业网站的建设 英文摘要思路#xff1a;其实就是判断反转链表是不是和原链表一样的问题。
我们可以借助反转链表的思路#xff0c;首先我们先把链表的全部元素正向存储#xff0c;然后再把链表进行反转。
之后我们再遍历反转之后的链表结点元素是不是和刚刚存储数组里面的元素一致就可以了。一旦…思路其实就是判断反转链表是不是和原链表一样的问题。
我们可以借助反转链表的思路首先我们先把链表的全部元素正向存储然后再把链表进行反转。
之后我们再遍历反转之后的链表结点元素是不是和刚刚存储数组里面的元素一致就可以了。一旦有一个不一致的就说明不是。否则就是可以。
这个做法的缺点就是消耗的空间复杂度较大。
/*** 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) {int []arrnew int[100010];ListNode tmphead;int len0;while(tmp!null){arr[len]tmp.val;tmptmp.next;}ListNode a1null;ListNode a2head;while(a2.next!null){ListNode tmp1a2.next;ListNode tmp2a2;a2.nexta1;a2tmp1;a1tmp2;}a2.nexta1;int i0;while(a2!null){if(a2.val!arr[i]){return false;}i;a2a2.next;}return true;}
}
思路二
快慢指针这里的快慢指针用来查找链表的中点。快指针每次走2步慢指针每次走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(headnull||head.nextnull)return true;ListNode nimanew ListNode(-1);nima.nexthead;ListNode slownima;ListNode fastnima;while(fast!nullfast.next!null){//奇数长度和偶数长度区别判断slowslow.next;fastfast.next.next;}fastslow.next;slow.nextnull;slownima.next;ListNode tmp1fast;ListNode tmp2null;while(tmp1.next!null){ListNode a1tmp1.next;ListNode a2tmp1;tmp1.nexttmp2;tmp1a1;tmp2a2;}tmp1.nexttmp2;while(tmp1!null){if(tmp1.val!slow.val)return false;tmp1tmp1.next;slowslow.next;}return true;}
}
