JAVA OJ练习第8题——链表的回文结构_acm回文链表 oj java

牛客链接：链表的回文结构

测试样例：
1->2->2->1
返回：true

方法一：

思路：
1）第一步，找到中间节点
2） 第二步，逆置链表后半部分节点
3） 第三步，判断链表是否是回文结构

代码如下：

import java.util.*;

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        if(A == null) {
            return false;
        }
        if(A.next == null) {
            return true;
        }
        //找到单链表的中间节点
        ListNode fast = A;
        ListNode slow = A;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //反转单链表
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //fast/slow/往前   head往后
        while(slow != A){
            if(A.val!=slow.val) {
                return false;
            }
            if(A.next == slow) {
                return true;
            }
            slow = slow.next;
            A = A.next;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

方法二：

思路：
利用额外空间，定义一个长度相同数组保存链表的数据，判断数组回文。

代码如下：

import java.util.*;
 
//利用额外空间
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        ListNode p = A;                 //指向表头
        int len = 0;                    //记录表长
        while(p != null){
            len ++;
            p = p.next;
        }
        //定义一个长度相同数组保存链表的数据
        int[] a = new int[len];
        for(int i=0; i<len; i++){
            a[i] = A.val;
            A = A.next;
        }
        //转化为判断数组回文
        for(int i=0; i<len/2; i++){
            if(a[i] != a[len-1-i]){
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

---

下一题：相交链表