leetcode234题-简单方法判断回文链表

目录

题目

分析

代码实现

---

题目

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

提示:
链表中节点数目在范围 [1,105] 内，0<= Node.val <= 9
要求：

时间复杂度：O(n)

空间复杂度：O(1)

分析

要满足复杂度的要求，我们可以反转从中间节点开始的子链表，将子链表与原链表对比，判断是否为回文链表。（此时并没有开辟新的链表节点，都是在原链表基础上操作的）

---

第一步：找出链表的中间结点

//找出中间点
public ListNode middleNode(ListNode head) {
    ListNode f = head;
    ListNode l = head;
    while (f != null && f.next != null) {
        f = f.next.next;
        l = l.next;
    }
    return l;
}

 

---

 

第二步：反转从中间结点开始的子链表

//反转
public ListNode reverList(ListNode head) {
    if(head ==null||head.next ==null){
        return head;
    }
    ListNode prev = null;
    ListNode cur = head;
    while(cur !=null){
        ListNode next = cur.next;
        cur.next = prev;//断线
        prev = cur;
        cur = next;
    }
    return prev;
}

---

第三步：对比原链表与子链表的值

遍历对比原链表与子链表

//遍历对比
public boolean isPalindrome(ListNode head) {
    ListNode midHead = middleNode(head);
    ListNode newHead = reverList(midHead);
    while (newHead != null) {
        if (head.val != newHead.val) {
        return false;
    }
    newHead = newHead.next;
    head  = head.next;
    }
    return true;
}

代码实现

三步方法结合解出题目答案

class Solution {
    //遍历对比
    public boolean isPalindrome(ListNode head) {
        ListNode midHead = middleNode(head);
        ListNode newHead = reverList(midHead);
        while (newHead != null) {
            if (head.val != newHead.val) {
                return false;
            }
            newHead = newHead.next;
            head = head.next;
        }
        return true;
    }
    //反转
    public ListNode reverList(ListNode head) {
        if(head ==null||head.next ==null){
            return head;
        }
        ListNode prev = null;
        ListNode cur = head;
        while(cur !=null){
            ListNode next = cur.next;
            cur.next = prev;//断线
            prev = cur;
            cur = next;
        }
        return prev;
    }
    //中间点
    public ListNode middleNode(ListNode head) {
        ListNode f = head;
        ListNode l = head;
        while (f != null && f.next != null) {
            f = f.next.next;
            l = l.next;
        }
        return l;
    }
}

​

时间复杂度：O(n)。

空间复杂度：O(1)。