判断回文链表

发表于 阅读次数：

题目

给定一个链表的头节点head,请判断该链表是否为回文结构。

例子: 1->2->1,返回true，1->2->2->1,返回true，1->2->3，返回false。

额外条件： 如果链表长为N，时间复杂度达到O(N),额外空间复杂度到达O(1)。

思路

拿到题目，我们先看一下数据状况，可以发现，回文结构，就是具有对称性的集合，
这边有3种思路。

①最简单的解法就是利用栈先进后出的特点。拿链表值的倒序和正序对比。空间复杂度到达O(N)。

isPalindrome1

②用快慢指针和栈，设置两个指针，遍历链表，慢的一次一步，快的一次两步。当快的走到底时，慢指针正好处于中心处，然后快指针停止移动，慢指针在后半程移动的同时把遍历的值放入栈中，最后把栈的值和链表的值遍历对比。空间复杂度到达O(N/2)

isPalindrome2

③用快慢指针，找到中间节点，然后慢指针遍历后半程的时候把后半段的链表反转。然后头尾同时开始遍历对比，最后把后半段还原。空间复杂度O(1)

isPalindrome3

下面看下具体的实现

实现

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }

    public Node reverseList(Node node) {

        Node prev = null;
        Node next = null;
        while(node != null) {
            next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }
        return prev;
    }

    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

    public static boolean isPalindrome1(Node node) {

        Stack<Node> stack = new Stack<>();
        Node temp = node;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }

        while(node != null) {
            if(stack.pop().value!= node.value) {
                return false;
            }
            node = node.next;
        }
        return true;
    }

    public static boolean isPalindrome2(Node node) {

        if(node == null || node.next == null) {
            return true;
        }
        Node slow = node;
        Node fast = node;
        Stack<Node> stack = new Stack<>();
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        while(slow != null) {
            stack.push(slow);
            slow = slow.next;
        }

        while(!stack.isEmpty()) {
            if(node.value != stack.pop().value) {
                return false;
            }
            node = node.next;
        }
        
        return true;
    }

    public static boolean isPalindrome3(Node node) {

        if(node.next == null || node == null) return true;

        Node fast = node;
        Node slow = node;

        //1 2 3 4
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //slow已经指向中间（奇）或者中间前一个(偶)了，所以往后一位就开始要反转了
        fast = slow.next;
        //中间那一位不需要指向next了
        slow.next = null;
        Node after = null;
        while (fast != null) {
            //保存后一个位置先
            after = fast.next;
            //反转：指向slow，因为我们再前面就把fast = slow.next了
            fast.next = slow;
            //slow指向当前位置，也就是保存上一个位置
            slow = fast;
            //指向之前保存的下一位
            fast = after;
        }
        //after保存尾节点为还原备用，因为结束上面的循环后fast指向的是为节点的next，所以fast为null，而slow指向为节点
        after = slow;
        //fast作为头节点
        fast = node;
        boolean ret = true;
        //尾节点和头节点
        while(fast != null && slow != null) {
            if(fast.value != slow.value) {
                ret = false;
                break;
            }
            fast = fast.next;
            slow = slow.next;
        }

        //还原链表,现在尾节点为after,下面slow存了倒数第二个节点
        slow = after.next;
        after.next = null;

        //这里用fast保存当前节点的后一个节点
        while(slow != null) {
            fast = slow.next;
            //后一个的next指向前一个
            slow.next = after;
            after = slow;
            //下一个节点走起
            slow = fast;
        }
        return ret;
    }

    public static void main(String[] args) {

        Node head = null;
        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(2);
        head.next.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.println(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");

    }