题解 | #判断一个链表是否为回文结构#

两种方法解答

方法一：辅助数组

方法二：快慢指针，翻转链表

import java.util.*;

/*

• public class ListNode {
• int val;
• ListNode next = null;
• } */

public class Solution {

//翻转链表
public ListNode reverse(ListNode head){
    ListNode pre = null;
    ListNode cur = head;
    ListNode cur_next = null;
    while(cur!=null){
        cur_next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = cur_next;
    }
    return pre;   
}

public boolean isPail (ListNode head) {
    // write code here
    // 方法一 辅助数组
    ArrayList<Integer> arr = new ArrayList<>();
    while(head!=null){
        arr.add(head.val);
        head = head.next;
    }
    int index=0, len = arr.size();
    int mid=len/2;
    while(index<mid){
        if(!arr.get(index).equals(arr.get(len-index-1)))
            return false;
        index++;
    }
    return true;
    
    
    
    //方法二 先通过快慢指针法寻找链表中点，将链表分为左右两份，接着将第二份链表翻转，最后比较
    if(head==null || head.next==null)
        return true;
    ListNode slow = head;
    ListNode fast = head.next;
    while(fast!=null && fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode right_head = slow.next;
    slow.next = null;
    ListNode left = head;
    ListNode right = reverse(right_head);
    while(right!=null){//要么左右结点个数相等，要么左边比右边结点数多一个，所以判断右边就可以了
        if(left.val!=right.val)
            return false;
        left = left.next;
        right = right.next;
    }
    return true;
}

}