淘先锋技术网

首页 1 2 3 4 5 6 7

目录

1 题目描述

2 解题思路

3 代码实现


1 题目描述

对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。

给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。

2 解题思路

大的方向分为3步:① 找到中间结点 ② 对单链表后半部分进行反转 ③ 链表向中间推进判断值是否相等

具体:

  • 在找中间结点的时候,可以定义两个结点fast和slow,让fast结点从头结点开始每次走两步,slow结点从头结点开始每次走一步,最终slow所在的结点就是中间结点,不论单链表的个数是奇数个还是偶数个。
  • 进行反转操作时,我们对将要进行反转的结点设为p,它要指向前一结点(中间结点slow),即p.next = slow,但此时p结点要向后推进继续进行反转操作,所以我们需要再定义一个结点pNext = p.next。当需要反转的结点p不为null时,进行反转,且在此时:当p.next不为null时,才可以进行p结点的移动,直到p结点为null,单链表遍历完毕,且进行了后半部分的反转操作。
  • 在进行值是否相等的判断中,需要分单链表是奇偶数的情况:首先通过while外层循环判断奇数个单链表,在循环里面判断偶数个单链表,进行相应的值比较即可。

3 代码实现

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        ListNode fast = A;
        ListNode slow = A;
        //找到中间结点
        while(fast != null&&fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode p = slow.next;
        //对后半部分链表进行反转
        while(p != null){
            ListNode pNext = p.next;
            p.next = slow;
            slow = p;
            p = pNext;
            if(p != null){
                pNext = p.next;
            }
        }
        //链表向中间推进判断值是否相等
        while(A != slow){
            if(A.val != slow.val){
                return false;
            }
            if(A.next == slow){
                return true;
            }
            A = A.next;
            slow = slow.next;
        }
        return true;
    }
}