题解 | #判断一个链表是否为回文结构#

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

https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f

思路

  • 既然要判断链表是否为回文结构,只需要把链表反转,将链表与反转链表一一对应即可
  • 当然,这样需要使用反转链表,而且需要复制一个链表,所以可以把链表中的元素倒入数组中倒序复制一份进行逐个对比,这样也可以

代码

import java.util.*;

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

public class Solution {
    /**
      * @param head ListNode类 the head
      * @return bool布尔型
      */
    public boolean isPail(ListNode head) {
        // 代码健壮性检验
        if (head == null) {
            return false;
        }
        if (head.next == null) {
            return true;
        }
        // 头节点
        ListNode temp1 = head;
        ListNode temp2 = new ListNode(-9999);
        ListNode flag = temp2;
        // 复制一份链表
        while (true) {
            temp2.next = new ListNode(temp1.val);
            if (temp1.next == null) {
                break;
            }
            temp2 = temp2.next;
            temp1 = temp1.next;
        }
        // 将传入的链表反转
        ListNode reverseList = reverseList(head);

        while (flag.next != null) {
            flag = flag.next;
            if (flag.val != reverseList.val) {
                return false;
            }
            reverseList = reverseList.next;
        }
        return true;
    }

    /**
     * 反转链表
     *
     * @param head 第一个数据节点
     * @return com.gewuyou.algorithm.problem.ListNode
     * @apiNote
     * @since 2022/12/20 10:42
     */
    public ListNode reverseList(ListNode head) {
        // 代码健壮性检验
        if (head == null) {
            return null;
        }
        // 标记当前节点
        ListNode current = head;
        // 设置前一节点
        ListNode previous = null;
        while (current != null) {
            //记录当前节点的下一个节点
            ListNode temp = current.next;
            //让当前节点指向前一个节点
            current.next = previous;
            //将前一个节点设置为当前节点
            previous = current;
            //将当前节点向下移动
            current = temp;
        }
        // 当当前节点为空时,表示当前节点到原链表尾+1位置了,返回前一个节点即是反转后的链表头
        return previous;
    }
}
全部评论

相关推荐

11-15 17:19
湖南大学 Java
成果成果成果果:这是哪个公司的hr,这么离谱吗,我没见过用性别卡技术岗的,身边女性同学拿大厂offer的比比皆是
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务