It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.
As a countermeasure, it seems that a site called Let Code will take measures.
A site that trains algorithmic power that can withstand coding tests that are often done in the home.
I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.
Leet Code Table of Contents Starting from Zero
Last time Leet Code Day 29 "46. Permutations" starting from zero
Basically, I would like to solve the easy acceptance in descending order.
Twitter I'm doing it.
You will be given a unidirectional linked list, so check if it is a palindrome.
Example 1:
Input: 1->2 Output: false
Example 2:
Input: 1->2->2->1 Output: true
The easiest way is to return True
if it matches the flipped list of the given linked list, or False
if it doesn't.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
value = []
while head:
value.append(head.val)
head = head.next
return value == value[::-1]
# Runtime: 92 ms, faster than 15.28% of Python3 online submissions for Palindrome Linked List.
# Memory Usage: 24.1 MB, less than 11.54% of Python3 online submissions for Palindrome Linked List.
I didn't have a little time this time, so I'll bring someone else's answer from discuss.
For example, the answer to O (1).
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head):
rev = None
fast = head
while fast and fast.next:
fast = fast.next.next
rev, rev.next, head = head, rev, head.next
tail = head.next if fast else head
isPali = True
while rev:
isPali = isPali and rev.val == tail.val
head, head.next, rev = rev, head, rev.next
tail = tail.next
return isPali
# Runtime: 92 ms, faster than 15.28% of Python3 online submissions for Palindrome Linked List.
# Memory Usage: 24.1 MB, less than 11.54% of Python3 online submissions for Palindrome Linked List.
https://leetcode.com/problems/palindrome-linked-list/discuss/64500/11-lines-12-with-restore-O(n)-time-O(1)-space
The contents of this discussion are recommended as an easy-to-understand explanation. It's amazing that it's easy to understand visually ...
https://leetcode.com/problems/palindrome-linked-list/discuss/324358/O(n)-time-and-O(1)-space-with-explanation-(Python-and-C)
Later, there were multiple solutions in the linked list chapter of this book.
150 questions to train your programming skills to fight in the world
If you have time, you may want to check it out.
Recommended Posts