平台网站建设需要什么技术,成都最新的防疫通告今天,做外贸网站企业,直播教育网站建设目录 题目#xff1a; 我们直接看题解吧#xff1a; 解题方法#xff1a; 难度分析#xff1a; 审题目事例提示#xff1a; 解题分析#xff1a; 解题思路#xff08;数组列表双指针#xff09;#xff1a; 代码说明补充#xff1a; 代码实现#xff1a; 代码实现 我们直接看题解吧 解题方法 难度分析 审题目事例提示 解题分析 解题思路数组列表双指针 代码说明补充 代码实现 代码实现快慢指针 题目地址 234. 回文链表 - 力扣LeetCode 难度简单 今天刷回文链表大家有兴趣可以点上看看题目要求试着做一下。
题目 给定一个链表的 头节点 head 请判断其是否为回文链表。 如果一个链表是回文那么链表节点序列从前往后看和从后往前看是相同的。 我们直接看题解吧 解题方法 方法1、复制链表到数组列表后用双指针 方法2、递归 方法3、快慢指针 难度分析 递归解法比较难理解快慢指针主要是代码量过多 审题目事例提示 最后返回false或者true即可 解题分析 解题思路数组列表双指针 主要分两步·复制链表到数组列表 ·利用双指针判断是否回文 创建一个存储整型对象的列表vals 循环遍历链表依次将链表的值赋给列表 创建双指针并初始化front0backvals.size()-1即分别指向列表一前一后 循环遍历列表如果front 与back指针指向值不等则return false 最后return true 代码说明补充 注意在编码的过程中注意我们比较的是节点值的大小而不是节点本身。正确的比较方式是node_1.val node_2.val而 node_1 node_2 是错误的。 代码实现
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {ListInteger vals new ArrayListInteger(); //创建列表// 将链表的值复制到数组中ListNode currentNode head; //创建链表节点指针移动指针方便遍历while (currentNode ! null) {vals.add(currentNode.val);currentNode currentNode.next;}// 使用双指针判断是否回文int front 0;int back vals.size() - 1;while (front back) {if (!vals.get(front).equals(vals.get(back))) {//利用get()与equals()方法return false;}front;back--;}return true;}
}
代码实现递归
class Solution {private ListNode frontPointer;private boolean recursivelyCheck(ListNode currentNode) {if (currentNode ! null) {if (!recursivelyCheck(currentNode.next)) {return false;}if (currentNode.val ! frontPointer.val) {return false;}frontPointer frontPointer.next;}return true;}public boolean isPalindrome(ListNode head) {frontPointer head;return recursivelyCheck(head);}
}
代码实现快慢指针
class Solution {public boolean isPalindrome(ListNode head) {if (head null) {return true;}// 找到前半部分链表的尾节点并反转后半部分链表ListNode firstHalfEnd endOfFirstHalf(head);ListNode secondHalfStart reverseList(firstHalfEnd.next);// 判断是否回文ListNode p1 head;ListNode p2 secondHalfStart;boolean result true;while (result p2 ! null) {if (p1.val ! p2.val) {result false;}p1 p1.next;p2 p2.next;} // 还原链表并返回结果firstHalfEnd.next reverseList(secondHalfStart);return result;}private ListNode reverseList(ListNode head) {ListNode prev null;ListNode curr head;while (curr ! null) {ListNode nextTemp curr.next;curr.next prev;prev curr;curr nextTemp;}return prev;}private ListNode endOfFirstHalf(ListNode head) {ListNode fast head;ListNode slow head;while (fast.next ! null fast.next.next ! null) {fast fast.next.next;slow slow.next;}return slow;}
}
