Palindrome Linked List
Implement a function to check if a linked list is a palindrome.
Example
Given 1->2->1, return true
Challenge
Could you do it in O(n) time and O(1) space?
思路:
先找到中间节点middle,然后把middle之后从middle.next到最后给reverse。然后两个链表一个一个元素比较。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { /** * @param head a ListNode * @return a boolean */ public boolean isPalindrome(ListNode head) { if (head == null) { return true; } if (head.next == null) { return true; } ListNode middle = getMiddle(head); ListNode reverseHead = reverseList(middle.next); while (head != null && reverseHead != null) { if (head.val != reverseHead.val) { return false; } else { head = head.next; reverseHead = reverseHead.next; } } return true; } public ListNode getMiddle(ListNode head) { if (head == null) { return head; } ListNode p1 = head, p2 = head; while (p1.next != null && p1.next.next != null) { p1 = p1.next.next; p2 = p2.next; } return p2; } public ListNode reverseList(ListNode head) { if (head == null) { return head; } ListNode prev = null; while (head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; } return prev; } } |