链表训练5：三种方法带你优雅判断回文链表
【题目描述】
给定一个链表的头节点 head, 请判断该链表是否为回文结构。
例如：
1->2->1，返回 true.
1->2->2->1, 返回 true。
1->2->3，返回 false。
【要求】
如果链表的长度为 N, 时间复杂度达到 O(N)。
【解答】
方法1
我们可以利用栈来做辅助，把链表的节点全部入栈，在一个一个出栈与链表进行对比，例如对于链表 1->2->3->2->2，入栈后如图:
然后再逐一出栈与链表元素对比。
这种解法比较简单，时间复杂度为 O(n), 空间复杂度为 O(n)。
代码如下
//方法1
public static boolean f1(Node head) {
if (head == null || head.next == null) {
return true;
}
Node temp = head;
Stack stack = new Stack<>();
while (temp != null) {
stack.push(temp);
temp = temp.next;
}
while (!stack.isEmpty()) {
Node t = stack.pop();
if (t.value != head.value) {
return false;
}
head = head.next;
}
return true;
} 方法二
真的需要全部入栈吗？其实我们也可以让链表的后半部分入栈就可以了，然后把栈中的元素与链表的前半部分对比，例如 1->2->3->2->2 后半部分入栈后如图：
然后逐个出栈，与链表的前半部分(1->2)对比。这样做的话空间复杂度会减少一半。
代码如下：
//方法2
public static boolean f(Node head) {
if(head == null || head.next == null)
return true;
Node slow = head;//慢指针
Node fast = head;//快指针
Stack stack = new Stack<>();
//slow最终指向中间节点
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
System.out.println(slow.value);
slow = slow.next;
while (slow != null) {
stack.push(slow);
slow = slow.next;
}
//进行判断
while (!stack.isEmpty()) {
Node temp = stack.pop();
if (head.value != temp.value) {
return false;
}
head = head.next;
}
return true;
} 方法三：空间复杂度为 O(1)。
上道题我们有作过链表的反转的，没看过的可以看一下勒：【链表问题】如何优雅着反转单链表]，我们可以把链表的后半部分进行反转，然后再用后半部分与前半部分进行比较就可以了。这种做法额外空间复杂度只需要 O(1), 时间复杂度为 O(n)。
代码如下:
//方法3
public static boolean f2(Node head) {
if(head == null || head.next == null)
return true;
Node slow = head;//慢指针
Node fast = head;//快指针
//slow最终指向中间节点
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
Node revHead = reverse(slow.next);//反转后半部分
//进行比较
while (revHead != null) {
System.out.println(revHead.value);
if (revHead.value != head.value) {
return false;
}
head = head.next;
revHead = revHead.next;
}
return true;
}
//反转链表
private static Node reverse(Node head) {
if (head == null || head.next == null) {
return head;
}
Node newHead = reverse(head.next);
head.next.next = head;
head.next = null;
return newHead;
}这道题被问的概率也是挺高的，就算代码写不出，也得至少知道思路
问题拓展
思考：如果给你的是一个环形链表，并且指定了头节点，那么该如何判断是否为回文链表呢？
如果喜欢本网站{https://www.iamshuaidi.com), 那么可以把该网站分享给其他人，帅地正在疯狂更新中….