数据结构 单链表的回文结构_单向链表 回文

  链表的回文结构，即 1 --> 2 --> 3 --> 2 --> 1 这样的形式，链表正着和反过来是一样的。

1 时间复杂度 O(N)

思路：
1、将原链表进行拷贝；
2、对拷贝的链表进行逆置；
3、然后比较逆置之后的链表和原链表是否相同。

public boolean chkPalindrome(ListNode A) {
// 1 判断特殊情况，即链表为空和链表只有一个结点的情况
//   此时，必定是回文结构
    if (A == null || A.next == null) {
        return true;
    }

// 2 先拷贝一份原链表，不破坏原来的链表
    ListNode newHead = new ListNode(0);
    ListNode newTail = newHead;
    for(ListNode node = A;node != null;node = node.next) {
        newTail.next = new ListNode(node.val);
        newTail = newTail.next;
    }

// 3 用三指针法，即 prev、cur、next 来逆置链表
    ListNode prev = null;
    ListNode cur = newHead.next;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    ListNode curReverseA = prev;

// 4 比较逆置之后的链表和原链表是否相同
    ListNode curA = A;
    while (curReverseA != null && curA != null) {
        if (curA.val == curReverseA.val) {
            curA = curA.next;
            curReverseA = curReverseA.next;
        } else {
            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
27
28
29
30
31
32
33
34
35
36
37

2 时间复杂度 O(1)

思路：
1、不用新创建链表，直接在原链表上进行操作；
2、求得链表的长度，然后读取到一半的元素；
3、对一半的元素进行逆置；
4、然后将逆置后的半个链表与剩下的未逆置的一半链表进行比较。

private static int getLength(ListNode head) {
    int length = 0;
    for (ListNode cur = head;cur != null; cur = cur.next) {
        length ++;
    }
    return length;
}

public static boolean chkPalindrome(ListNode A) {

// 1、先将特殊情况考虑罗列出来
    if (A == null || A.next == null) {
        return true;
    }

// 2、读取到前半个链表
    int len = getLength(A);
    int steps = len / 2;
    ListNode B = A;
    for (int i = 0; i < steps; i++) {
        B = B.next;
    }

// 3、将这前半个链表进行逆置
    ListNode prev = null;
    ListNode cur = B;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    B = prev;

// 4、比较逆置了的前半个链表和未逆置的后半个链表
    ListNode cur1 = A;
    ListNode cur2 = B;
    while (cur1 != null && cur2 != null) {
        if (cur1.val != cur2.val) {
            return false;
        }
        cur1 = cur1.next;
        cur2 = cur2.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
40
41
42
43
44
45

注意：
  链表结点为奇数个和偶数个的时候，链表的样子是不一样的，但是代码是一致的。

  偶数个时，因为 cur1 != null && cur2 != null 这个条件，只要一个为null，循环就会结束了。