[数据结构与算法]BM13 判断一个链表是否为回文结构

描述

给定一个链表，请判断该链表是否为回文结构。

回文是指该字符串正序逆序完全一致。

数据范围： 链表节点数 0 \le n \le 10^50≤n≤105，链表中每个节点的值满足 |val| \le 10^7∣val∣≤107

示例1

输入：

{1}

返回值：

true

复制

示例2

输入：

{2,1}

返回值：

false

说明：

2->1     

示例3

输入：

{1,2,2,1}

返回值：

true

说明：

1->2->2->1     

方法1（用数组存储，头尾遍历）

时间复杂度o(n)

空间复杂度o(n)

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param head ListNode类 the head
 * @return bool布尔型
 */
bool isPail(struct ListNode* head ) {
    // write code here
    int len=0;
    struct ListNode* cur=head;
    while(cur){
        len++;
        cur=cur->next;
    }
    int arr[len];
    int i=0;
    cur=head;
    while(cur){
        arr[i++]=cur->val;
        cur=cur->next;
    }
    int j=len-1;
    i=0;
    while(j>i){
       if(arr[i]!=arr[j]){
           return false;
       } 
        j--;
        i++;
    }
    return true;
    
}

方法二（快慢指针法，找到链表的中间点位置）

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public ListNode reverse(ListNode head){
        ListNode pre=null;
        while(head!=null){
            ListNode q=head.next;
            head.next=pre;
            pre=head;
            head=q;
        }
        return pre;
    }
    public boolean isPail (ListNode head) {
        // write code here
        ListNode fast=head;
        ListNode slow=head;
        //遍历到链表中间点位置
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
       if(fast!=null) //如果快指针不为空，则链表个数为奇数
           slow=slow.next;  //向后移动一位
        
        fast=head;
        ListNode cur=reverse(slow);  //后面的链表翻转
        while(cur!=null){   //前后链表循环遍历
            if(cur.val!=fast.val)
                 return false;
            cur=cur.next;
            fast=fast.next;
         }
        return true;
    }
}