LeetCode--234. Palindrome Linked List

本文主要是介绍LeetCode--234. Palindrome Linked List，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem：

Given a singly linked list, determine if it is a palindrome.
Follow up: Could you do it in O(n) time and O(1) space?

Analysis：

判断一个单向链表是否是回文链表，要求O（n）的时间复杂度和O（1）的空间复杂度。
算法有以下几种：

1. 遍历整个链表，将链表每个节点的值记录在数组中，再判断数组是不是一个回文数组，时间复杂度为O（n），但空间复杂度也为O（n），不满足空间复杂度要求。
2. 利用栈先进后出的性质，将链表前半段压入栈中，再逐个弹出与链表后半段比较。时间复杂度O（n），但仍然需要n/2的栈空间，空间复杂度为O（n）。
3. 反转链表法，将链表后半段原地翻转，再将前半段、后半段依次比较，判断是否相等，时间复杂度O（n），空间复杂度为O（1）满足题目要求。

Answer：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
public class Solution {public boolean isPalindrome(ListNode head) {//判断特殊情况，head空链表活着只有一个值即为回文链表if(head==null || head.next==null) return true;//只有两个值的链表下面的判断错误，需要单独判断if(head.next.next==null) return head.val==head.next.val;//利用快慢指针确定链表中心ListNode slow = head;ListNode fast = head;while(fast.next!=null && fast.next.next!=null){fast = fast.next.next;slow = slow.next;}//将后半段倒置后头节点赋值给闲置的slowslow=reverselist(slow.next);// 虽然比较的是head（整段）和slow，但是比较函数按照最短处理了return isSame(head,slow);}//将后半段链表原地倒置public ListNode reverselist(ListNode node){ListNode temp;ListNode pre=null;ListNode cur=node;while(cur!=null){temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;}//比较链表前半段和后半段是否相同public boolean isSame(ListNode fa,ListNode sl){while(sl!=null){if(fa.val==sl.val){fa = fa.next;sl = sl.next;}else return false;}return true;}
}

经验：

• 快慢指针寻找中心
• 原地倒置链表
• 分函数解体

这篇关于LeetCode--234. Palindrome Linked List的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---