A.每日一题：234. 回文链表

题目链接234. 回文链表简单算法原理本题与 A.每日一题876. 链表的中间结点2130. 链表最大孪生和 中的 2130题基本一模一样只是在部分地方有修改这里就不过多赘述了大家可以自行参考上面这篇博客~~解法一双指针顺序表7ms击败35.92%时间复杂度O(N)解法二递归17ms击败6.07%时间复杂度O(N)解法三迭代5ms击败59.18%时间复杂度O(N)Java代码/** * 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 { //234. 回文链表 //解法一双指针顺序表 public boolean isPalindrome(ListNode head) { ListInteger listnew ArrayList(); ListNode curhead; while(cur!null){ list.add(cur.val); curcur.next; } int left0,rightlist.size()-1; while(leftright){ if(list.get(left)!list.get(right)) return false; left;right--; } return true; } }/** * 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 { //234. 回文链表 //解法二递归 private ListNode left; public boolean isPalindrome(ListNode head) { lefthead; return dfs(head); } private boolean dfs(ListNode right){ //递先把right移到链表末尾 if(right.next!null!dfs(right.next)) return false; //归从右到左遍历链表 if(left.val!right.val) return false; //left 往右走 leftleft.next; //归right会往左走 return true; } }/** * 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 { //234. 回文链表 //解法三递归 public boolean isPalindrome(ListNode head) { ListNode midmiddleNode(head); ListNode head2reverseList(mid); while(head2!null){ if(head.val!head2.val) return false; headhead.next; head2head2.next; } return true; } //876.链表的中间结点 private ListNode middleNode(ListNode head){ ListNode slowhead; ListNode fasthead; while(fast!nullfast.next!null){ slowslow.next; fastfast.next.next; } return slow; } //206.反转链表 public ListNode reverseList(ListNode head) { ListNode prenull; ListNode curhead; while(cur!null){ ListNode nxtcur.next; cur.nextpre; precur; curnxt; } return pre; } }