LC 234. 回文链表

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

示例 1:
输入: 1->2
输出: false

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

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

class Solution {
    //反转链表
    public ListNode reverseList(ListNode head){
        ListNode curr = head, pre = null;
        while(curr != null){
            ListNode temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;
        }
        return pre;
    }
    public boolean isPalindrome(ListNode head) {
        if(head == null){
            return false;
        }
        //找到中间节点,1,3,4,5,4,3,1
        //遍历完后,curr指向节点5
        ListNode curr = head, temp = head;
        while(temp != null && temp.next != null){
            curr = curr.next;
            temp = temp.next.next;
        }
        //将curr指向的后半段链表反转,反转后的链表为1,3,4,1,3,4,5
        temp = reverseList(curr);
        while(temp != null){
            //从头开始与head链表比较
            if(head.val != temp.val){
                return false;
            }
            head = head.next;
            temp = temp.next;
        }
        return true;
    }
}

LC 234. 回文链表

上一篇:b_lc_骑士通关(贪心+懒惰思想)


下一篇:b_lc_绝对差值和(贪心)