【数据结构】链表：LeetCode题（四）234.回文链表

落日映苍穹つ 2022-11-03 00:48 150阅读 0赞

## [234. 回文链表][234.] ##

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

**示例 1:**

输入: 1->2
    输出: false

**示例 2:**

输入: 1->2->2->1
    输出: true

### 解法一：栈 ###

*  思路：遍历链表，将所有节点压入栈，再遍历一遍进行对比  
    注：栈里应该存的是val，而不是ListNode，因为比较的时候顺序是相反的，ListNode肯定都不相同。
 *  复杂度
    
     *  Time：O（n）
     *  Space：O（n），用了个Stack

public boolean isPalindrome(ListNode head) {
        
            // 注：栈里存的是具体value，是Stack<Integer>，不是Stack<ListNode>
            Stack<Integer> stack = new Stack<>();
            // 注：链表用for遍历更简洁
            for (ListNode p = head; p != null; p = p.next) 
                stack.push(p.val);
            for (ListNode p = head; p != null; p = p.next)
                if (p.val != stack.pop())
                    return false;
            return true;
        }

### 解法二：折半对比 ###

*  思路：先将链表前一半反转，然后从中间开始同时进行遍历比较（双指针）。但是要注意一点，若长度是奇数情况，则要将后面的指针（cur）后移一位
 *  复杂度
    
     *  Time：O（n）
     *  Space：O（1）

public boolean isPalindrome(ListNode head) {
        
            // 1.计算链表长度
            int len = 0;
            for (ListNode p = head; p != null; p = p.next) len++;
    		
            // 2.将链表前一半倒序，反转链表的模板
            ListNode cur = head, pre = null;
            for (int i = 0; i < len / 2; i++) {
        
                ListNode tmp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = tmp;
            }
    		
        	// 注：若长度是奇数，则要将cur后移一位再比较
            if (len % 2 == 1) cur = cur.next;
        	// 3.从中间开始同时遍历前一半与后一半，比较val
            for (; pre != null && cur != null; pre = pre.next, cur = cur.next) 
                if (pre.val != cur.val)
                    return false;
    
            return true;
        }

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