This article has participated in the Denver Nuggets Creators Camp 3 “More Productive writing” track, see details: Digg project | creators Camp 3 ongoing, “write” personal impact

describe

Given the head of a singly linked list, return true if it is a palindrome.

Example 1:

Input: head = [1,2,2,1]
Output: true
Copy the code

Example 2:

Input: head = [1,2]
Output: false
Copy the code

Note:

The number of nodes in the list is in the range [1, 10^5].
0 <= Node.val <= 9
Copy the code

parsing

A list of values is a palindrome sequence. The easy way to do this is to iterate through the list and put it in r, then iterate to see if r[I] and r[n-i-1] are equal. If you don’t want to wait for False, return True at the end of the loop.

answer

class ListNode(object): def __init__(self, val=0, next=None): self.val = val self.next = next class Solution(object): def isPalindrome(self, head): """ :type head: ListNode :rtype: bool """ if not head.next: return True r = [head.val] while head.next: head = head.next r.append(head.val) n = len(r) for i in range(n//2): if r[i]! =r[n-i-1]: return False return TrueCopy the code

The results

Linked List for the Linked List in the Python online submissions. Memory Usage: 10000 ms. Submissions in the Python online List for Palindrome Linked List.Copy the code

parsing

In fact, the above process can be simplified, just need to get the list of values in the linked list, directly reverse comparison can determine whether it is a palindrome linked list.

answer

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        result = []
        while head:
            result.append(head.val)
            head = head.next
        return result == result[::-1]
        
Copy the code

The results

Linked List for the Linked List in the Python online submission. Memory Usage: Submissions in the Python online List for Palindrome Linked List.Copy the code

parsing

The above two solutions are essentially the same, as you can see they are both fairly slow because part of the time is spent organizing a new list, and the easiest solution is definitely a traversal. Here’s the idea:

  • Navigate to the middle of the list
  • Then reverse the list nodes in the last half to form a new list
  • Compare the new linked list with the previous half, equal is palindromic linked list

Obviously the speed and memory used has been significantly improved.

answer

class ListNode(object): def __init__(self, val=0, next=None): self.val = val self.next = next class Solution(object): def isPalindrome(self, head): """ :type head: ListNode :rtype: bool """ if not head or not head.next: return True def reverseList(self, head): newhead=None while head: p=head head=head.next p.next=newhead newhead=p return newhead slow=fast=head while fast and fast.next: fast=fast.next.next slow=slow.next if fast: slow=slow.next newhead=reverseList(self,slow) while newhead: if newhead.val! =head.val: return False newhead=newhead.next head=head.next return TrueCopy the code

The results

Linked List for the Linked List in the Python online submission. Memory Usage: 10000 ms. Submissions in Python online submissions for Palindrome Linked List.Copy the code

Original link: leetcode.com/problems/pa…

Your support is my biggest motivation