Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: Palindrome Linked List

Posted on February 17, 2018July 26, 2020 by braindenny

Palindrome Linked List



Similar Problems:

  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: #palindrome

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?

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## https://code.dennyzhang.com/palindrome-linked-list
## Basic Ideas: Find the middle node. Reverse the right part. Then compare with the left part
##       From: a->b->c->b->a
##       To:   a->b->c->a->b
## Complexity: Time O(n), Space O(1)

# 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 head is None or head.next is None:
            return True
        # find length
        length = 0
        p = head
        while p:
            length += 1
            p = p.next

        dummy = ListNode(None)
        dummy.next = head

        p = dummy
        for i in xrange((length+1)/2):
            p = p.next
        q = p
        p = dummy
        # move sublist to the head
        ## dummy -> a -> b
        ##   p      q    r
        for i in xrange(length/2):
            r = q.next
            q.next = r.next
            r.next = p.next
            p.next = r
        # move 2 pointers
        p = dummy
        for i in xrange(length/2):
            p = p.next
        q = p
        p = dummy
        for i in xrange(length/2):
            if p.next.val != q.next.val:
                return False
            p = p.next
            q = q.next
        return True
linkedin
github
slack

Post Views: 2
Posted in MediumTagged #linkedlist, #palindrome

Post navigation

LeetCode: Valid Palindrome II
LeetCode: Find All Anagrams in a String

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.