LeetCode 回文链表

╰+攻爆jí腚メ 2023-10-11 12:22 40阅读 0赞

**回文链表题目描述：**  
**请判断一个链表是否为回文链表。  
示例 1:  
输入: 1->2  
输出: false  
示例 2:  
输入: 1->2->2->1  
输出: true**

**题目分析：判断一条链表是否为回文链表**  
**1、首先先利用快慢指针找到链表中间节点，慢指针要么指向中间节点、要么指向中间节点的前一个节点（与链表长度的奇偶数有关！）  
2、找到中间节点后，将链表从中间节点的下一个结点开始的后半条链表反转。（如果不懂链表反转可以点击这里：[反转链表][Link 1]）  
3、然后将前半段链表和后半段链表进行比较，完全相同就是回文链表。**

**java代码实现如下：**

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public boolean isPalindrome(ListNode head) {
           //如果链表只有一个有效节点或者不存在有效节点，那么就直接返回false
            if (head == null || head.next == null) {
                return true;
            }
            //通过快慢指针找到中间节点
            ListNode quick = head;
            ListNode slow = head;
            while (quick != null && quick.next != null) {
                //快指针比慢指针快一倍，快指针指向nuLl的时候慢指针就是指向链表中点
                quick = quick.next.next;
                slow = slow.next;
            }
            //找到指针中点之后。从slow 开始对后面的链表进行反转
            ListNode tempHead = null;
            ListNode p = slow;
            while (p != null) {
                ListNode cur = p.next;//保存后面的节点，防止丢失
                p.next = tempHead;
                tempHead = p;
                p = cur;
            }
    
            //得到了新的链表tempHead 然后将前后两条链表进行比对，完全相同为true 否则为false
            while (tempHead != null) {
                if (tempHead.val == head.val) {
                    tempHead = tempHead.next;
                    head = head.next;
                } else {
                    return false;
                }
            }
            return true;
         }
    }

[Link 1]: https://blog.csdn.net/One_castle/article/details/101100557