Given a singly linked list, determine if it is a palindrome.
[分析] 利用two pointers 方式找出链表的中间节点,接着翻转后半段链表,最后比较前后两半,如果完全相同则满足回文性质。注意到比较前后两半时以后半段长度为准,因为链表长度为奇数时,前半段会多一个节点。 Method2 是参考
http://blog.csdn.net/u013027996/article/details/46832437的实现,更加简洁,且不需要考虑长度奇数偶数问题,记slow初始标号为1, fast则为2,经过n次循环后,slow=1 + n, fast=2 + 2*n, 第一个while循环结束后,若input链表长度为偶数,则slow.next是后半段链表的起始节点,fast指向最后一个节点;若为奇数,则slow.next最终指向链表的中间节点,fast指向倒数第二个节点。最后判断两段链表是否相同时,若为奇数,则后半段会多一个,但不要紧,因为前半段遍历完while循环即结束。
// Method 2
public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) return true;
ListNode slow = head, fast = slow.next;
while (fast != null && fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode curr = slow.next; //p is the start of second half or the middle element
ListNode next = null;
ListNode head2 = null;
while (curr != null) {
next = curr.next;
curr.next = head2;
head2 = curr;
curr = next;
}
while (head != null && head2 != null) {
if (head.val != head2.val) return false;
head = head.next;
head2 = head2.next;
}
return true;
}
}
// Method 1
public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null)
return true;
if (head.next.next == null)
return head.val == head.next.val ? true : false;
// split input list
ListNode p = head, q = head;
while (q != null) {
if (q.next != null) {
if (q.next.next != null) {
p = p.next;
q = q.next.next;
} else { // size is even
break;
}
} else { // size is odd
break;
}
}
// reverse second half
ListNode prev = null, curr = p.next, next = null;
while (curr != null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// check if is palindrome
q = prev;
p = head;
while (q != null) {
if (p.val != q.val) return false;
p = p.next;
q = q.next;
}
return true;
}
}
分享到:
相关推荐
方法1 思路:将链表中的元素都保存list中,并判断这个list和反转后的list,是否相同,如果相同,则回文;否则,则不回文。...# Definition for singly-linked list. # class ListNode(object): # def __i
linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to...
reverse-linked-list-ii(Reverse a Sub-list) 141 环形链表 linked-list-cycle 142 环形链表 II linked-list-cycle-ii 143 重排链表 reorder-list 148 排序链表 sort-list 234 回文链表 palindrome-linked-list 双...
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
Palindrome linked list Linked List Cycle trees Convert Sorted Array to Binary Search Tree string and search First Bad Version Dynamic Programing *** Climbing Stairs Set Matrix Zeroes API System....
leetcode 2 sum c LeetCode 帮助文档 帮助文档存放在Help文件夹下。 文件名 文件描述 ...complexitypython.txt Python的一些常规操作的复杂度统计 ...Linked List(链表) ...List ...Linked ...Palindrome Linked List
Leetcode 问题的 Python 解决方案 下面列出了这些问题的概述。 这些问题主要分为数据结构和算法两部分。 代码可以在此存储库的相应文件夹中找到。 数据结构: 细绳: 问题及解决方法: 242.有效字谜:| 409.最长回文...
[回文链表](md/Palindrome Linked List.md) - 2015-10-06 [数字一](md/数字一.md) - 2015-10-06 [使用栈实现队列](md/使用栈实现队列.md) - 2015-10-06 [BST 中的第 K 个最小元素](md/BST.md 中的第 K 个最小元素) -...
Palindrome Linked List 字符串 Valid Palindrome Implement strStr() String to Integer (atoi) Add Binary Longest Palindromic Substring Regular Expression Matching Wildcard Matching Longest Common Prefix ...
leetcode 面试清单 Java 比较器与比较器 哈希 静止的 例外 线 泛型 算法 链表 Linked List Cycle Remove Nth Node From End of List Merge Two Sorted Lists 两个链表的交集 Remove Duplicates from Sorted List ...
Palindrome Number C++ 2016/4/26 Easy 044 Wildcard Matching Python 2016/4/1 Hard 051 N-Queens C++ 2016/5/18 Hard 092 Reverse Linked List II Python 2017/11/28 Medium 095 Unique Binary Search Trees ...