首页 > 试题广场 >

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

[编程题]判断一个链表是否为回文结构
  • 热度指数：203245 时间限制：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
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
tjsz头像 tjsz
集合双指针解决 
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
没有offer不改名111头像 没有offer不改名111
为什么将列表转换为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)
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) {
        if (head == null || head.next == null) {
            return true;
        }
        if (head.next.next == null && head.next.val == head.val) {
            return true;
        }
        ArrayList<Integer> list = new ArrayList<>();
        ListNode tail = reverseListNode(head, list);
        int i = 0;
        while (tail != null) {
            if (tail.val == list.get(i)) {
                i++;
                tail = tail.next;
            } else {
                return false;
            }


        }
        return true;
    }
    public ListNode reverseListNode(ListNode head, ArrayList<Integer> list) {
        list.add(head.val);//1 2 3 4 5
        if (head.next == null || head == null) {
            return head;
        }
        ListNode tail = reverseListNode(head.next, list);
        head.next.next = head;
        head.next = null;
        return tail;
    }
}

发表于 2023-10-19 18:48:03 回复(0)
Java
牛客928346678号头像 牛客928346678号
反转节点后与原节点逐一对比:
import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 思路1: 反转节点后与原节点逐一对比
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        if(head == null) {
            return false;
        }
        
        // 反转列表
        ListNode rev = revNode(head);
        while(rev != null && rev.val == head.val) {
            rev = rev.next;
            head = head.next; 
        }
        return rev == null;
    }

    /**
        反转列表
     */
    public ListNode revNode(ListNode head) {
        ListNode cur = null;
        ListNode pre = null;
        while(head != null) {
            cur = new ListNode(head.val);
            cur.next = pre;
            pre = cur;
            head = head.next;
        }
        return cur;
    }
}
发表于 2023-10-15 01:48:35 回复(0)
Java
年轻的迪恩不愿再收感谢信头像 年轻的迪恩不愿再收感谢信
链表所有点分别放入栈和队列中，然后同步出栈和出队列，判断值是否相等。
发表于 2023-09-22 17:20:12 回复(0)
Java
光恰似水头像 光恰似水
结合反转例题做 
public boolean isPail (ListNode head) {
        // write code here
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        slow =  reserve(slow);
        fast = head;

        while (slow != null) {
            if (slow.val != fast.val) {
                return false;
            } else {
                slow = slow.next;
                fast = fast.next;
            }
        }
        return true;
    }
    static ListNode reserve(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

发表于 2023-09-13 18:45:38 回复(0)
Java
dqxfz头像 dqxfz
    public boolean isPail (ListNode head) {
        List<Integer> arr = new ArrayList();
        ListNode h = head;
        while (h != null) {
            arr.add(h.val);
            h = h.next;
        }
        for (int i = 0, j = arr.size() - 1; i <= j; i++, j--) {
            if (!arr.get(i).equals(arr.get(j))) {
                return false;
            }
        }
        return true;
    }
发表于 2023-09-13 10:09:35 回复(0)
Java
贪玩的莲雾最喜欢春天头像 贪玩的莲雾最喜欢春天
if(head==null ||head.next==null){
            return true;
        }
        List<Integer> list=new ArrayList<>();
        while(head!=null){
            list.add(head.val);
            head=head.next;
        }
        int i=0,j=list.size()-1;
        while(i<j){
            if(!list.get(i).equals(list.get(j)))
            {
                return false;
            }
            i++;
            j--;
        }
        return true;
发表于 2023-07-17 18:59:04 回复(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
        //1、判断头节点是否为空
        if (head == null) {
            return true;
        }
        //2、判断是否只有一个节点
        if (head.next == null) {
            return true;
        }
        //找到链表的中间节点
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode cur = slow.next;

        ListNode pre = slow;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;
        }
        fast = head;
        slow = pre;

        while (fast != slow) {
            if (fast.val != slow.val) {
                return false;
            }
            if (fast.next == slow) {
                return true;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }
}
发表于 2023-07-10 12:47:58 回复(0)
提交观点

问题信息

链表 双指针
难度：
114条回答 8825浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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