题解 | #链表的回文结构#

链表的回文结构

http://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa

方法一：

1、寻找中间结点并且标记起来--此处需要注意偶数个结点需要取两个中间值中的前一个

2、将链表根据中间结点进行分割成两个链表node1和node2

3、将后一个链表node2逆置--三指针法

4、比较node1和逆置后的node2的各个结点的val值

注意一些循环条件以及边界条件限制，具体问题具体分析

此方法时间复杂度o(N)，空间复杂度o(1)

import java.util.*;

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    
    //因为已经判断过了，所以A中至少有2个结点，分割后至少有1个结点，cur不可能为null
    public ListNode reserveNode(ListNode n){
        ListNode pre=null;
        ListNode cur=n;
        ListNode later=cur.next;
        while(cur.next!=null){
            cur.next=pre;
            pre=cur;
            cur=later;
            later=later.next;
        }
        cur.next=pre;
        return cur;
    }
    
    public boolean chkPalindrome(ListNode A) {
        //A为空或者A中只有一个结点
        if(A==null || A.next==null){  //假设链表为空时，为回文，如果为null直接指向next会报错
            return true;
        }
        
        //1.找到中间结点
        ListNode quick=A;
        ListNode slow=A;
        ListNode pre=null;
        while(quick!=null && quick.next!=null){
            pre=slow;
            slow=slow.next;
            quick=quick.next.next;
        }
        //如果链表结点个数为偶数个，需要取两个中间值的前一个
        if(quick==null){
            slow=pre;
        }
        
        //2.以slow所在中间值位置，分割链表--成两部分
        ListNode node1=A;
        ListNode node2=slow.next;
        slow.next=null;
        
        //3.逆置node2
        node2=reserveNode(node2);
        
        //4.比较node1和node2
        ListNode cur1=node1;
        ListNode cur2=node2;
        while(cur2!=null){
            if(cur1.val!=cur2.val){
                return false;
            }
            cur1=cur1.next;
            cur2=cur2.next;
        }
        return true;
    }
}

方法二：

利用题目给出的条件--链表长度小于等于900--给定大小为900的数组即可

空间复杂度也为o(1)，空间复杂度为o(n)

注意要计算链表长度--根据其长度判断是否回文

import java.util.*;

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        
        ListNode cur=A;
        //1.给定长度为900的数组，存放链表value
        int [] arr = new int[900];
        int size=0;
        while(cur!=null){
            arr[size++]=cur.val;
            cur=cur.next;
        }
        
        //2.判断回文
        int left=0;
        int right=size-1;
        while(left<=right){
            if(arr[left]!=arr[right]){
                return false;
            }
            left++;
            right--;
        }
        
        return true;
    }
}