Back at it again!

Linked List

Linked list is a linear data structure that are linked using pointers. Linked lists have nodes that are connected to each other. Each node has data and the address of the next node.

Unlike array, the size of linked list is dynamic and insertion/deletion is easy by traversing through the head of the list. However, random access is impossible and there will be extra memory due to the pointer in the linked list.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        
        
class LinkedList:
    def __init__(self):
        self.head = None

Insertion Deletion

Reverse Linked List

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

Example

Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]

Approach 1:

For linked list, I must always be careful about the case where there are 0 elements, only 1, and two elements within the linked list.

Given this, I will implement the iterative and the recursive implementation of reversed linked list.

Implementation:

# iterative
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
       prev, curr = None, head
       while curr:
           temp = curr.next
           curr.next = prev
           prev = curr
           curr = temp
           
       return prev
        

# recursive
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
       if not head:
           return None
       
       newH = head
       if head.next:
           newH = self.reverseList(head.next)
           head.next.next = head
       head.next = None
       return NewH
        

Complexity Analysis:

O(n) for time complexity

O(1) for space complexity when implemented with iterative approach, O(n) when recursive

Linked List Cycle Detection

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.

Return true if there is a cycle in the linked list. Otherwise, return false.

Approach 1:

For linked list, I must always be careful about the case where there are 0 elements, only 1, and two elements within the linked list.

Given this, I can implement an iterative method that uses hashset to check if the value is seen or not.

Implementation:

# iterative
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        while head:
            if head in seen:
                return True
            seen.add(head)
            head= head.next
        return False                

Complexity Analysis:

O(n) for time complexity

O(n) for space complexity

Approach 2:

I can have another approach where there are two pointers that move one-step and two-step at a time respectively. If they ever meet , there is a cycle whereas if the faster pointer reaches the end of the linked list, it has no cycle.

Implementation:

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head is None:
            return False
        slow, fast = head, head.next
        while slow != fast:
            if fast is None or fast.next is None:
                return False
            slow = slow.next
            fast = fast.next.next
        
        return True

Complexity Analysis:

O(n) for time complexity when no cycle O(n+k) when there is cycle

O(1) for space complexity