day13 leetcode-hot100-24（链表3）

234. 回文链表 - 力扣（LeetCode）

1.转化法

思路

        将链表转化为列表进行比较

复习到的知识

        arraylist的长度函数：list.size()

具体代码

/*** 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) {ListNode n = head;List<Integer> list = new ArrayList<>();while(n!=null){list.add(n.val);n=n.next;}int l=0;int r=list.size()-1;while(l<r){if(list.get(l)!=list.get(r)){return false;}l++;r--;}return true;}
}

 2.反转法

思路

        将后半段链表反转，然后进行比较。

知识

        取单链表的中间节点：快慢指针

具体代码

/*** 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) {ListNode n1 = secondL(head);ListNode n2 = reverseL(n1.next);ListNode p1 = head;ListNode p2 = n2;while(p2!=null){if(p1.val != p2.val){return false;}p1=p1.next;p2=p2.next;}return true;}public ListNode reverseL(ListNode l){ListNode old = null;ListNode current = l;while(current!=null){ListNode tem = current.next;current.next = old;old =current;current= tem;}return old;}public ListNode secondL(ListNode l){ListNode slow = l;ListNode fast = l;while(fast.next!=null && fast.next.next!=null){slow = slow.next;fast = fast.next.next;}return slow;}
}