LeetCode 234. 回文链表

Scroll Down

LeetCode 234. 回文链表

题目:

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

示例 1:

输入: 1->2
输出: false

示例 2:

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

双指针解法

首先使用双指针判断中间的指针值在哪,然后将后半段的指针进行反转,再与前半段的指针值进行比对,如果全部相等,则证明是回文链表.

public static boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null){
            return true;
        }
        ListNode fast1 = head;
        ListNode slow1 = head;
        ListNode slow2 = head;
        //先判断中间链表节点在哪里
        while(fast1 != null && fast1.next != null){
            fast1 = fast1.next.next;
            slow1 = slow1.next;
        }
        //反转后半段链表
        slow1 = reverseList(slow1);
        //当slow2指针走到中间指针时,证明已经到头了,可以停了
        ListNode slow1TempHead = slow1;
        while(slow1 != null && slow1TempHead != slow2){
            //判断是否正常
            if(slow1.val != slow2.val){
                return false;
            }
            slow1 = slow1.next;
            slow2 = slow2.next;
        }
        return true;
    }

    public static ListNode reverseList(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode curr = head;
        ListNode prev = null;
        while(curr != null){
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }

    public static ListNode reverseNodeByRe(ListNode node) {
        if (node == null || node.next == null) {
            return node;
        }
        ListNode curr = reverseNodeByRe(node.next);
        node.next.next = node;
        node.next = null;
        return curr;
    }

复杂度

时间复杂度:O(n)

空间复杂度:O(1)