链表：判断一个链表是否为回文结构

题目：给定一个链表头节点 head，请判断链表是否为回文结构

例如：

1-->2-->1，返回 true；

1-->2-->2-->1，返回 true；

15-->6-->15，返回 true；

1-->2-->3，返回 false；

进阶：

如果链表长度为 N，时间复杂度为 O（N），额外空间复杂度为 O（1）；

方法一：

利用栈结构，将链表节点全部压入栈内，再重新从头遍历链表同时与栈内弹出的数据进行比较，如果该链表是一个回文结构则整个比较过程都为真，否则的话肯定有不相等的结点。

时间复杂度O（N），空间复杂度O（N）

 1 class Node
 2 {
 3     public int data;
 4     public Node next;
 5 
 6     public Node(int data)
 7     {
 8         this.data = data;
 9     }
10 }
11 
12 public boolean isPalindrome(Node head)
13 {
14     if(head == null || head.next == null)
15         return true;
16 
17     Stack<Node> stack = new Stack<>();
18     Node cur = head;
19     while(cur != null)
20     {
21         stack.push(cur);
22         cur = cur.next;
23     }
24 
25     cur = head;
26     while(!stack.isEmpty())
27     {
28         if(stack.pop().data != cur.data)
29         return false;
30         cur = cur.next;
31     }
32     return true;
33 }

方法二：

方法二是方法一的优化版，虽然也是栈结构，但我们选择只将一半的节点压入即可

 1 public boolean isPalindrome(Node head)
 2 {
 3     if(head == null || head.next == null)
 4         return true;
 5 
 6     Stack<Node> stack = new Stack<>();
 7     Node fast = head, slow = head.next;
 8     while(fast.next != null && fast.next.next != null)
 9     {
10         slow = slow.next;
11         fast = fast.next.next;
12     }
13 
14     while(slow != null)
15     {
16         stack.push(slow);
17         slow = slow.next;
18     }
19 
20     while(!stack.isEmpty())
21     {
22         if(stack.pop().data != head.data)
23             return false;
24         head = head.next;
25     }
26     return true;
27 }

方法三：

我们也可以在O（N）时间复杂度和O（1）空间复杂度内解决此题，具体分析如下：

1. 改变链表右边区域的结构，使整个右半区反转，最后指向中间节点

如图

2. leftStart 和 rightStart 同时向中间遍历，每一步移动都比较当前节点的值，如果不一样则将标识量即为 false

3. 不管是否为回文，都需要将原链表恢复原样

 1 public boolean isPalindrome(Node head)
 2 {
 3     if(head == null || head.next == null)
 4         return true;
 5 
 6     Node fast = head, slow = head;
 7     while(fast.next != null && fast.next.next != null)
 8     {
 9         slow = slow.next;
10         fast = fast.next.next;
11     }
12 
13     Node cur = slow.next;
14     slow.next = null;
15     Node pre = slow, next = null;
16     while(cur != null)
17     {
18         next = cur.next;
19         cur.next = pre;
20         pre = cur;
21         cur = next;
22     }
23 
24     Node leftStart = head, rightStart = pre;
25     boolean flag = true;
26     while(leftStart != null && rightStart != null)
27     {
28         if(leftStart.data != rightStart.data)
29         {
30             flag = false;
31             break;
32         }
33         leftStart = leftStart.next;
34         rightStart = rightStart.next;
35     }
36     
37     cur = pre.next;
38     pre.next = null;
39     while(cur != null)
40     {
41         next = cur.next;
42         cur.next = pre;
43         pre = cur;
44         cur = next;
45     }
46 
47     return false;
48 }

参考资料：程序员代码面试指南 IT名企算法与数据结构题目最优解，左程云