剑指 Offer II 027. 回文链表
2022/1/22 23:34:19
本文主要是介绍剑指 Offer II 027. 回文链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
剑指 Offer II 027. 回文链表
给定一个链表的 头节点 head ,请判断其是否为回文链表。 如果一个链表是回文,那么链表节点序列从前往后看和从后往前看是相同的。
方法一:将值复制到数组中后用双指针法
列表的概要讲述:
有两种常用的列表实现,分别为数组列表和链表。如果我们想要在列表中存储值,它的实现是这样的:
- 数组列表底层是使用数组存储值,我们可以通过索引在 O(1) 的时间访问列表任何位置的值,这是由基于内存寻址的方式。
- 链表存储的是称为节点的对象,每个节点保存一个值和指向下一个节点的指针。访问某个特定索引的节点需要 O(n) 的时间,因为要通过指针获取到下一个位置的节点。
确定数组列表是否回文很简单,我们可以使用双指针法来比较两端的元素,并向中间移动。一个指针从起点向中间移动,另一个指针从终点向中间移动。这需要 O(n) 的时间,因为访问每个元素的时间是 O(1),而有 n 个元素要访问。
然而同样的方法在链表上操作并不简单,因为不论是正向访问还是反向访问都不是 O(1)。而将链表的值复制到数组列表中是 O(n),因此最简单的方法就是将链表的值复制到数组列表中,再使用双指针法判断。
大体的思路:
1.复制链表到数组列表中 2.使用双指针判断是否回文
具体的实现:
第一步,我们需要遍历链表将值复制道数组中,我们用 currentNode 指向当前的节点。每次迭代向数组中添加 currentNode.val 并更新currentNode = currentNode.next 。当currentNode==null 时停止循环。 第二步,我们在起点放个指针,在结尾放一个指针,每一次迭代判断两个指针指向的元素是否相同,若不同,return false。相同,则相反。相同则将两个指针向中间移动,并继续判断,直到两个指针相遇。
/** * 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) { List<Integer> list = new ArrayList<Integer>(); //遍历量表逐个将值放到数组中去 ListNode currnetNode = head; while(currnetNode!=null){ list.add(currnetNode.val); currnetNode=currnetNode.next; } //在数组的两端设置两个指针 int front = 0; int back =list.size()-1; while(front<back){ if(!list.get(front).equals(list.get(back))){ return false; }else{ front++; back--; } } return true; } }
方法二:递归
递归为我们提供了一种优雅的方式来方向遍历节点。
function print_values_in_reverse(ListNode head){ if(head!=null){ print_values_in_reverse(head.next); } }
如果使用递归反向迭代节点,同时使用递归函数外的变量向前迭代,就可以判断链表是否为回文。
实现思路:
currentNode 指针是先到尾节点,由于递归的特性是从后往前比较。frontPointer 是递归函数外的指针。 若currentNode.val != frontPointer.val 则返回false。 反之,frontPointer 向前移动并返回true。
/** * 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 { 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); } }
这篇关于剑指 Offer II 027. 回文链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)