回文链表

柔光的暖阳◎ 2022-12-03 09:18 181阅读 0赞

# 回文链表 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/palindrome-linked-list/

## 2、题目 ##

> **题目要求**

请判断一个链表是否为回文链表。

> **示例 1：**

输入：1->2

输出：false

> **示例 2:**

输入: 1->2->2->1

输出: true

> **进阶：**

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

## 3、代码思路 ##

方法一：

1.  遍历链表，将其中的数据存入 `ArrayList` 中，然后对 `ArrayList` 进行回文判断即可(双指针法)
2.  遍历整个链表，将其添加至 `ArrayList` 中的时间复杂度为 O(n)，因为 `ArrayList` 底层使用数组存储，访问任一元素的时间复杂度为 O(1)，使用双指针法判回文的时间复杂度为 O(n/2)，所以整个算法复杂度为 O(n)
3.  因为额外开辟了 `ArrayList` 的空间，所以需要额外 O(n) 的空间

--------------------

方法二：

1.  想要将空间复杂度降为 O(1)，意思就是要在原链表上进行回文判断，我们可以将链表的后半部分反转(修改链表结构)，然后将前半部分和后半部分进行比较。
2.  首先，我们需要找到中间的链表节点，对此我们可以使用两种方法：第一，先求得链表长度，除以 `2` 便得到中间节点的索引；第二，使用快慢指针，慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针到链表的中间
3.  然后翻转后半部分的链表，同时从链表首部和中间遍历，挨个比较各个节点的值，判断链表是否回文链表
4.  恢复链表，虽然不需要恢复也能通过测试用例，因为使用该函数的人不希望链表结构被更改。

--------------------

方法三：

## 4、代码实现 ##

方法一：

/**
     * @ClassName IsPalindromeDemo
     * @Description TODO
     * @Author Heygo
     * @Date 2020/9/2 20:41
     * @Version 1.0
     */
    public class IsPalindromeDemo {
        
    
        public static void main(String[] args) {
        
            ListNode head = new ListNode(129);
            head.next = new ListNode(129);
    
            boolean isPalindrome = isPalindrome(head);
            System.out.println(isPalindrome);
        }
        
        /**
         * 判断链表是否为回文链表
         * @param head 链表首节点
         * @return true：回文链表；false：不是回文链表
         */
        public static boolean isPalindrome(ListNode head) {
        
            // 将链表中的值加入到 ArrayList 中
            List<Integer> vals = new ArrayList<>();
            ListNode curNode = head;
            while (curNode != null) {
        
                vals.add(curNode.val);
                curNode = curNode.next;
            }
    
            // 双指针判断回文数组
            int left = 0;
            int right = vals.size() - 1;
            while (left < right) {
        
                if (vals.get(left).equals(vals.get(right))) {
        
                    left++;
                    right--;
                } else {
        
                    return false;
                }
            }
    
            return true;
        }
    
    
        public static class ListNode {
        
            int val;
            ListNode next;
    
            ListNode(int x) {
        
                val = x;
            }
        }
    
    }

--------------------

方法二：

/**
     * @ClassName IsPalindromeDemo
     * @Description TODO
     * @Author Heygo
     * @Date 2020/9/2 20:41
     * @Version 1.0
     */
    public class IsPalindromeDemo {
        
    
        public static void main(String[] args) {
        
            ListNode head = new ListNode(1);
            head.next = new ListNode(2);
            head.next.next = new ListNode(2);
            head.next.next.next = new ListNode(1);
    
            boolean isPalindrome = isPalindrome(head);
            System.out.println(isPalindrome);
        }
    
        /**
         * 判断链表是否为回文链表
         * @param head 链表首节点
         * @return true：回文链表；false：不是回文链表
         */
        public static boolean isPalindrome(ListNode head) {
        
            // 获取中间节点
            ListNode middleNode = findMiddleNode(head);
            // 翻转后半部分链表
            ListNode secondHead = reverse(middleNode);
    
            // 前半部分与后半部分相比较
            ListNode frontPointer = head;
            ListNode backPointer = secondHead;
    
            while (backPointer != null) {
        
                if (frontPointer.val == backPointer.val) {
        
                    frontPointer = frontPointer.next;
                    backPointer = backPointer.next;
                } else {
        
                    return false;
                }
            }
            return true;
        }
    
        /**
         * 找出链表中间的节点，
         * 如果链表长度为 n，则返回第 n/2 个节点，索引从 0 开始
         *
         * @param head 链表首节点
         * @return 中间节点
         */
        public static ListNode findMiddleNode(ListNode head) {
        
    
            ListNode slow = head;
            ListNode fast = head;
    
            // fast 每走两步，slow 走一步
            while (fast != null && fast.next != null) {
        
                slow = slow.next;
                fast = fast.next.next;
            }
    
            return slow;
        }
    
        /**
         * 翻转链表
         * @param head 链表首节点
         * @return 翻转后的链表首节点
         */
        public static ListNode reverse(ListNode head) {
        
    
            ListNode pre = null;
            ListNode cur = head;
    
            while (cur != null) {
        
                // 保存 cur.next
                ListNode tempNode = cur.next;
                // 让 cur 指向 pre
                cur.next = pre;
                // pre 指针后移
                pre = cur;
                // cur 指针后移
                cur = tempNode;
            }
    
            // 遍历完后，cur == null，pre 恰好指向新的链表头
            return pre;
        }
    
        public static class ListNode {
        
            int val;
            ListNode next;
    
            ListNode(int x) {
        
                val = x;
            }
        }
    
    }

\`\`