欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【LeetCode】234.回文链表

程序员文章站 2022-04-17 15:52:24
...

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

示例 1:

输入: 1->2     输出: false

示例 2:

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

【LeetCode】234.回文链表       【LeetCode】234.回文链表

 代码如下:

class Solution {
    public boolean isPalindrome(ListNode head) {
        //如果是一条空链表或是只有一个节点的链表就认为是回文链表     
        if(head==null||head.next==null){ 
            return true; 
        } 
        ListNode slow=head;
        ListNode fast=head;
        //找中点位置
        while(fast.next!=null &&fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        //逆置链表
        ListNode reverseNode=reverseList(slow);
        //进行比较
        while(head!=null && reverseNode!=null){
            if(head.val!=reverseNode.val){
                return false;
            }
            head=head.next;
            reverseNode=reverseNode.next;
        }
        return true;
    }
    //将链表进行逆置
    public ListNode reverseList(ListNode head){
        if(head==null){
            return head;
        }
        ListNode pre=head;
        ListNode cur=head.next;
        ListNode temp;
        while(cur!=null){
            temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        head.next=null;
        return pre;
    }
}