首页 > 试题广场 >

判断一个链表是否为回文结构

[编程题]判断一个链表是否为回文结构
  • 热度指数：230075 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
数据范围： 链表节点数 ，链表中每个节点的值满足
示例1

输入

{1}

输出

true
示例2

输入

{2,1}

输出

false

说明

2->1
示例3

输入

{1,2,2,1}

输出

true

说明

1->2->2->1

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
Java
牛客203596504号头像 牛客203596504号
用堆栈存储前一半的数据，然后快慢指针一次遍历就解决。
前半程一边遍历一边入栈，直到快指针撞到终点。(这有个细节，如果是奇数要跳过正中的那个数)
后半程继续遍历一边弹栈对比。
import java.util.*;

public class Solution {

    public boolean isPail (ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode slow = head;
        ListNode fast = head.next.next;
        int[] stack = new int[50000];
        stack[0] = slow.val;
        int offset = 0;
        while (fast != null) {
            slow = slow.next;
            if (fast.next == null) break;
            fast = fast.next.next;
            stack[++offset] = slow.val;
        }
        slow = slow.next;
        while (slow != null) {
            if (slow.val != stack[offset--]) return false;
            slow = slow.next;
        }
        return true;
    }

}


发表于 2025-11-21 18:43:10 回复(0)
Java
hang柒头像 hang柒
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        if(head==null||head.next==null){
            return true;
        }
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode slow=dummy;
        ListNode fast=dummy;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode mid=slow.next;
        ListNode head2= reverse(mid);
        while(head2!=null&&head!=null){
            if(head.val!=head2.val){
                return false;
            }
            head=head.next;
            head2=head2.next;
        }
        return true;
    }

    private ListNode reverse(ListNode head){
        ListNode pre=null;
        while(head!=null){
            ListNode next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }
}
发表于 2025-09-02 11:23:37 回复(0)
Java
BraveCoder头像 BraveCoder 
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // 处理空链表（视为回文）
        if (head == null) {
            return true;
        }
        
        // 步骤1：将链表节点的值存入数组
        List<Integer> values = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            values.add(current.val);
            current = current.next;
        }
        
        // 步骤2：使用双指针判断数组是否为回文
        int left = 0;
        int right = values.size() - 1;
        while (left < right) {
            // 若对应位置的值不相等，则不是回文
            if (!values.get(left).equals(values.get(right))) {
                return false;
            }
            left++;   // 左指针右移
            right--;  // 右指针左移
        }
        
        // 所有对应位置的值都相等，是回文
        return true;
    }
}

发表于 2025-08-07 17:16:36 回复(0)
Java
QbitCoding头像 QbitCoding 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        List<ListNode> list=new ArrayList<ListNode>();
        while(head!=null){
            list.add(head);
            head=head.next;
        }
        for(int i=0;i<list.size()/2;i++){
            if(list.get(i).val!=list.get(list.size()-i-1).val){
                return false;
            }
        }
        return true;
    }
}
把链表转成数组，感觉在作弊啊
发表于 2025-05-17 14:53:30 回复(0)
Java
能干的社畜头像 能干的社畜
小白，对链表不是很熟悉。所以就把链表先转换成自己熟悉的List，然后对首尾的值进行对比来判断是 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        if (head == null) return true;

        // 定义一个List来存放链表的值
        ArrayList<Integer> values = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            values.add(current.val);
            current = current.next;
        }

        // 判断列表是否为回文
        int left = 0;
        int right = values.size() - 1;
        while (left < right) {
            if (!values.get(left).equals(values.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

不是回文~
发表于 2025-03-18 16:44:04 回复(0)
Java
ZhenGG头像 ZhenGG 
public class Solution {
    /**
     * 直接用定义：先逆序创建个链表，再依次对比。
     *
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        if(head==null)return true;
        ListNode revser = new ListNode(head.val);
        ListNode cur = head;
        while(cur.next!=null){
            cur = cur.next;
            ListNode temp = new ListNode(cur.val);
            temp.next = revser;
            revser = temp;
        }
        cur=head;
        while(cur!=null){
            if(revser.val!=cur.val)return false;
            cur = cur.next;
            revser = revser.next;
        }
        return true;
    }
}
发表于 2024-10-04 12:21:00 回复(0)
Java
牛客136246826号头像 牛客136246826号 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        ArrayList<Integer> array = new ArrayList<>();
        while (head != null) {
            array.add(head.val);
            head = head.next;
        }

        if (array.size() == 1) {
            return true;
        }

        if (array.size() % 2 == 0) {
            for (int i = 0; i < array.size() / 2 ; i++) {
                if (Math.abs(array.get(i)) !=Math.abs(array.get(array.size() -1 - i))) {
                    return false;
                }
            }
        } else {
            for (int i = 0 ; i <= array.size() / 2; i++) {
                 if (Math.abs(array.get(i)) !=Math.abs(array.get(array.size() -1 - i))) {
                    return false;
                }
            }
        }
        return true;
    }
}

发表于 2024-09-03 17:04:53 回复(0)
Java
cwygzdcsx头像 cwygzdcsx
集合双指针解决 
public class Solution {
    public boolean isPail (ListNode head) {
        // write code here
        List<Integer> list = new ArrayList<Integer>();
        while(head!=null){
            list.add(head.val);
            head=head.next;
        }
        int length = list.size();
        for(int i=0;i<length;i++){
            if((int)list.get(i) != (int)list.get(length-1-i)){
                return false;
            }
        }
        return true;
    }
}


发表于 2024-08-27 14:57:52 回复(0)
Java
牛客348570162号头像 牛客348570162号 
public boolean isPail (ListNode head) {
        return isPail2(head);
    }

    //破坏链表
    public boolean isPail2 (ListNode head) {
        if(head.next == null) return true;
        ListNode new_head = new ListNode(999);
        ListNode slow = head,fast = head.next;
        while(true){
            if(fast == null){ // 奇数个
                slow = slow.next;
                break;
            }
            if(fast.next == null){ // 偶数个
                ListNode tmp = slow.next;
                slow.next = new_head.next;
                new_head.next = slow;
                slow = tmp;
                break;
            }
            ListNode tmp = slow.next;
            slow.next = new_head.next;
            new_head.next = slow;
            slow = tmp;
            fast = fast.next.next;
        }
        fast = new_head.next;
        while(fast != null){
            if(fast.val != slow.val ) return false;
            fast = fast.next;
            slow = slow.next;
        }
        return true; 
    }

    //转数组
    public boolean isPail1 (ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        for(int i=0,j=list.size()-1;i <= j;i++,j--){
            if(list.get(i) - list.get(j) != 0){
                return false;
            }
        }
        return true;
    }

发表于 2024-08-20 09:14:48 回复(0)
Java
人间水长东头像 人间水长东 
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here

        // 使用栈获得链表逆序，并一一比较判断回文

        // 算法的时间复杂度O(N)，空间复杂度O(N)

        // 1.对于null和单节点链表，必回文
        if (head == null && head.next == null) {
            return true;
        }

        // 2.第一次遍历，结点依次入栈
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        // 3.第二次遍历，结点依次出栈，比较是否相同
        cur = head;
        while (cur != null) {
            ListNode stackNode = stack.pop();
            if (cur.val != stackNode.val) {
                return false;
            }
            cur = cur.next;
        }

        // 4.若遍历完都没发现不同的结点，则是回文
        return true;
    }
}

发表于 2024-07-27 00:21:45 回复(0)
Java
牛客839384289号头像 牛客839384289号 
public boolean isPail (ListNode head) {
    // write code here
    ListNode p1=head;
    Stack<ListNode> stack=new Stack<>();
    while(p1!=null){
        stack.push(p1);
        p1=p1.next;
    }
    while(!stack.isEmpty()){
        if(stack.pop().val!=head.val){
            return false;
        }
        head=head.next;
    }
    return stack.isEmpty();
}

发表于 2024-06-02 13:15:38 回复(0)
Java
Sowhyn头像 Sowhyn
为什么将列表转换为list然后用双指针AC不了呢
发表于 2024-05-03 15:12:23 回复(1)
Java
风雨尘头像 风雨尘 
public boolean isPail (ListNode head) {
    // write code here
    if (head==null) return false;

    List<Integer> list = new ArrayList<>();
    list.add(head.val);
    while (head.next != null) {
        list.add(head.next.val);
        head = head.next;
    }

    for(int i = 0, j = list.size() - 1; i < list.size(); i++,j--) {
        if(!list.get(i).equals(list.get(j))) {
            return false;
        }
    }

    return true;
}

编辑于 2024-04-15 18:25:13 回复(1)
Java
迷人的代码渣渣躺平又起来了头像 迷人的代码渣渣躺平又起来了
public boolean isPail (ListNode head) {
        // write code here
        // 投个巧转成数组做了
        List<Integer> lis = new ArrayList<>();
        while(head!=null){
            lis.add(head.val);
            head = head.next;
        }
       
        int start = 0;
        int end = lis.size()-1;
        for(;start<end;start++,end--){
            if(lis.get(start).equals(lis.get(end))){
                continue;
            }else{
                return false;
            }
        }
        return true;
    }
发表于 2024-01-20 17:04:11 回复(0)
Java
一代码夫头像 一代码夫
 1.链表进行反转
 2.反转后的链表和原始链表中的节点值一一对比，相同则表示是回文结构
 3.借助数组实现链表的反转
编辑于 2023-12-06 15:50:53 回复(0)
Java
牛客276339250号头像 牛客276339250号
要判断是否是回文，链表反转后和反转前一致其实就是回文链表，
import java.util.*;

/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类 the head
* @return bool布尔型
*/
public boolean isPail (ListNode head) {
ListNode newList = ReverseList(head);
while (head != null) {
if (head.val != newList.val) {
return false;
}
head = head.next;
newList = newList.next;
}
return true;
}
public ListNode ReverseList (ListNode head) {
ListNode pre=null;
ListNode cur=head;
while(cur!=null){
ListNode node = new ListNode(cur.val);
node.next=pre;
cur=cur.next;
pre=node;
}
return pre;
}
}
发表于 2023-11-12 23:10:39 回复(0)
Java
BlueProtocol头像 BlueProtocol
理应该是这种方法 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        if(head == null || head.next == null) return true;
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=null&&fast.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode suffixPart = slow.next;
        slow.next = null;
        ListNode reverseSuffixPart  = reverse(suffixPart);
        while(head!=null && reverseSuffixPart!=null) {
            if(head.val != reverseSuffixPart.val) return false;
            head = head.next;
            reverseSuffixPart = reverseSuffixPart.next;
        }

        return true;
    }
    public ListNode reverse(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode reverseListNode = null;
        ListNode tempListNode = null;
        while(head!=null) {
            tempListNode = head.next;
            head.next = reverseListNode;
            reverseListNode = head;
            head = tempListNode;
        }
        return reverseListNode;
    }

}


发表于 2023-11-04 15:42:12 回复(1)
Java
进入人才池头像 进入人才池 
public class Solution {
    public boolean isPail (ListNode head) {
        if ( head == null || head.next == null ) return true;
        ListNode right = cutList(head);
        while ( head != null && right != null ) {
            if ( head.val != right.val ) return false;
            head = head.next;
            right = right.next;
        }
        // left, right 一样长，或者 right 多一个
        return right == null || right.next == null;
    }
    ListNode cutList(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // 找中点
        ListNode fast = dummy, slow = dummy;
        while ( fast != null && fast.next != null ) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 断开
        ListNode right = slow.next;
        slow.next = null;

        // 反转right
        return reverse(right);
    }
    ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head, nxt = null;
        while ( cur != null ) {
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

发表于 2023-11-03 15:37:51 回复(0)
提交观点

问题信息

链表 双指针
难度：
121条回答 12080浏览

热门推荐

通过挑战的用户

查看代码

相关试题

判断一个链表是否为回文结构

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号