各位如果看到博客内有广告,可以动手点一点,谢谢

MENU

LeetCode234. 回文链表

August 8, 2018 • Read: 325 • LeetCode

题目链接:LeetCode234


 如何用O(1)的空间复杂度才是难点,首先定义两个指针,一个快指针high,一个慢指针low,快指针每次走两个节点,慢指针每次走一个,这样当快指针指向最后一个节点的时候,慢指针指向了中点,然后再定义一个tmp指针,首先将将中点的next指向null,然后将中点以后的链表指针全部翻转,都做完了以后从第一个节点和最后一个节点同时出发进行遍历,如果中途有值不一样就直接返回false,终止条件是这两个指针不等于null,因为指向中点的下一个节点就是null

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null)
            return true;
        ListNode low = head;//快指针,每次走两个节点
        ListNode high = head;//慢指针,每次走一个节点
        while(high.next != null && high.next.next != null) {
            low = low.next;//find mid
            high = high.next.next;//find end
        }
        high = low.next;
        low.next = null;
        ListNode tmp = null;
        while(high != null) {//swap 
            tmp = high.next;
            high.next = low;
            low = high;
            high = tmp;
        }
        tmp = low;
        high = head;
        boolean res = true;
        while(low != null && high != null) {
            if(low.val != high.val) {
                res = false;
                break;
            }
            high = high.next;
            low = low.next;
        }
        return res;
    }
}
Archives Tip
QR Code for this page
Tipping QR Code