本文主要是介绍定个小目标之每天刷LeetCode热题(3),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
这是一道简单题,我这里就只讲两种解法
第一种是数组加双指针,先遍历链表将值存到数组里,然后分别从数组两端进行一一比较判断是否满足回文,代码实现
class Solution {public boolean isPalindrome(ListNode head) {List<Integer> vals = new ArrayList<Integer>();// 将链表的值复制到数组中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))) {return false;}front++;back--;}return true;}
}
第二种是快慢指针加链表反转,相比第一种会复杂点,但是节省了空间,先使用快慢指针确定前半部分链表的尾节点,这里需要注意当链表节点数为奇数时,则中间的节点看作是前半部分,然后对后半部分链表进行反转,最后分别从前半部分链表头节点和后半部分链表头节点开始依次进行遍历比较判断是否满足回文,无论是否是回文链表,我们都应该恢复链表,流程图如下,代码如下
class Solution {public ListNode reverseList(ListNode head) {ListNode temp = null;ListNode p = head, q = head.next;while(p.next != null) {p.next = temp;temp = p;p = q;q = q.next;}p.next = temp;return p;}public boolean isPalindrome(ListNode head) {ListNode h1 = head, h2 = null, end = null, p = head, q = head;if (h1.next == null) return true;//找到前半部分链表的尾节点while(q != null && q.next != null && q.next.next != null) {p = p.next;q = q.next;q = q.next;}h2 = p.next;end = p;end.next = null;//反转后半部分链表h2 = reverseList(h2);//判断是否回文p = h1;q = h2;while(p != null && q != null && p != q) {if (p.val != q.val) {//恢复链表end.next = reverseList(h2);return false;}p = p.next;q = q.next;}//恢复链表end.next = reverseList(h2);return true;}
}
题目链接:题单 - 力扣(LeetCode)全球极客挚爱的技术成长平台
这篇关于定个小目标之每天刷LeetCode热题(3)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!