Alibi

My Life is Getting Better

Leetcode[234] Palindrome Linked List

29 Nov 2015

###Task1 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?

###Python ####O(n) space, O(n) time

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        stack = []
        itr = head
        while itr:
            stack.append(itr.val)
            itr = itr.next
        itr = head
        while itr:
            if stack.pop() != itr.val:
                return False
            itr = itr.next
        return True

####O(1) space O(n) time

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return True
        fast, slow = head.next, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        prev = None
        cur = slow.next
        while cur:
            temp = cur.next
            cur.next = prev
            prev = cur
            cur = temp
        p1, p2 = head, prev
        while p2 and p1.val == p2.val:
            p1, p2 = p1.next, p2.next
        return p2 == None

###Java

/**
 * 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) {
        if (head == null) {
            return true;
        }
        Stack<Integer> stack = new Stack<Integer>();
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            stack.push(slow.val);
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null && !stack.isEmpty()) {
            slow = slow.next;
        }
        while (slow != null && !stack.isEmpty()) {
            int cur = stack.pop();
            if (cur != slow.val) {
                return false;
            }
            slow = slow.next;
        }
        return true;
        
    }
}

###Points 1). 使用快慢指针寻找链表中点

2). 将链表的后半部分就地逆置，然后比对前后两半的元素是否一致

3). 恢复原始链表的结构（可选） * Two different ways to find the mid:
* slow, fast = head, head.next, stop until fast == none or fast.next == none
* slow, fast = head, head, stop until fast.next == none or fast.next.next == none * Four step reverse * When using stack, it can be done without iterate the entire list(in half)

Related Posts