第一种方法: 额外空间复杂度 O(N) , 遍历链表时, 将元素入栈, 再次遍历时, 从栈中弹出元素, 比较两者的大小, 就可以判断是不是回文链表
第二种方法: 利用快慢指针, 先找到链表的中间位置, 然后反转链表的后半部分, 再分别从链表两头遍历比较大小, 最后将链表恢复为原始结构
- public class PalindromeLinkedList {
- public static void main(String[] args) {
- Node head = new Node(1);
- head.next = new Node(3);
- head.next.next = new Node(5);
- head.next.next.next = new Node(5);
- head.next.next.next.next = new Node(3);
- head.next.next.next.next.next = new Node(1);
- display(head);
- // 快指针每次走二步, 慢指针每次走一步, 循环结束后, 当节点数量为奇数时, slow 来到了中间位置, 当节点数量为偶数时, slow 来到了中间位置 (虚线) 的前一个
- Node fast = head;
- Node slow = head;
- while(fast.next != null && fast.next.next != null){
- fast = fast.next.next;
- slow = slow.next;
- }
- // 这里的 slow 就表示中间节点, 记录 slow 的位置
- Node middle = slow;
- // 记录中间节点的下一个节点位置
- Node help = slow.next;
- // 中间节点指向 null
- slow.next = null;
- // 从 help 这个节点反转链表
- Node pre = null;
- Node next = null;
- // 循环结束后, pre 就是最后一个节点
- while(help != null) {
- next = help.next;
- help.next = pre;
- pre = help;
- help = next;
- }
- // 判断是否是回文
- boolean flag = true;
- Node first = head;
- Node second = pre;
- while(first != null && second != null) {
- if(first.value != second.value) {
- flag = false;
- break;
- }
- first = first.next;
- second = second.next;
- }
- System.out.println(flag);
- // 将链表恢复为原来的结构
- Node help_restore = pre;
- Node pre_restore = null;
- Node next_restore = null;
- while(help_restore != null) {
- next_restore = help_restore.next;
- help_restore.next = pre_restore;
- pre_restore = help_restore;
- help_restore = next_restore;
- }
- middle.next = pre_restore;
- display(head);
- }
- public static void display(Node head) {
- StringBuilder sb = new StringBuilder();
- while (head != null) {
- sb.append(head.value + "->");
- head = head.next;
- }
- String res = sb.substring(0, sb.lastIndexOf("->"));
- System.out.println(res);
- }
- public static class Node{
- public int value; // 值
- public Node next; // 下一个节点
- public Node(int value) {
- this.value = value;
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3231171.html