Classic Problems

本文蒐集

• LeetCode 206
• LeetCode 203
• LeetCode 328
• LeetCode 234

LeetCode 206: Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example:

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

我的解答

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
#         # iteratively
#         temp = head
        
#         while temp and temp.next:
#             temp2 = head
#             head = temp.next
#             temp.next = temp.next.next
#             head.next = temp2
#         return head
            
        # recursively
        return self._reverse(head)

    def _reverse(self, node, prev=None):
        if not node:
            return prev
        
        node.next, n = prev, node.next
        return self._reverse(n, node)

LeetCode 203: Remove Linked List Elements

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Example:

Constraints:

• The number of nodes in the list is in the range [0, \(10^4\)].
• 1 <= Node.val <= 50
• 0 <= k <= 50

我的答案

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:        
        while head and head.val == val:
            head = head.next
        
        if not head:
            return head
        
        perv = head
        node = head.next
        
        while node:
            if node.val == val:
                node = node.next
                perv.next = node
            else:
                perv = node
                node = node.next
        return head

LeetCode 328: Odd Even Linked List

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

Example:

Constraints:

• The number of nodes in the linked list is in the range [0, \(10^4\)].
• \(-10^6\) <= Node.val <= \(10^6\)

Follow up: Could you solve it in O(1) space complexity and O(nodes) time complexity?

我的解答

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head:
            return head

        perv = head
        node = second = head.next
        
        while node:
            perv.next = node.next
            perv = node
            node = node.next
        
        _ = head
        
        while _.next:
            _ = _.next
        
        _.next = second
        
        return head

LeetCode 234: Palindrome Linked List

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

Example:

Constraints:

• The number of nodes in the linked list is in the range [1, \(10^5\)].
• 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

我的解答

# 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:
        count = 0
        _ = head
        
        while _:
            _ = _.next
            count += 1
        
        if count == 1:
            return True
        
        else:
            perv = None
            node = head
            
            for i in range(count // 2):
                node = node.next
                head.next = perv
                perv = head
                head = node
    
            if count % 2 == 1:
                node = node.next
            
            while perv:
                if perv.val != node.val: 
                    return False
                perv = perv.next
                node = node.next
            
            return True