🌵
Christian's Wiki
/
📖
Data Structures & Algorithms
/
Algorithm
/
Linked List

Linked List

‣
Data Structure: What is a Linked List? What are the operations it supports and give their runtimes. Implement it
‣
What is the algorithm to reverse a linked list
  1. Start with 2 pointers at previous and current
  2. Enter a loop with the condition while current is not None:

      3. In the loop:

    1. We store a reference to the next node
    2. Change our current nodes next reference to our previous
    3. Reset our previous and current references for the next iteration
def reverseList(head: ListNode) -> ListNode:
        previous = None
        current = head
        
        while current is not None:
            next = current.next

            current.next = previous

						previous = current
            current = next
        
        return previous
‣
How do you get the middle of a linked list? What are the edge cases for this?
  1. Start with two pointers fast and slow
  2. Enter a loop with the condition while fast.next && fast.next.next

      3. In the loop

    1. Iterate through the list such that slow = slow.next and fast = fast.next and fast = fast.next
    2. The loop will terminate when
  3. Return the node referenced by slow.next if fast.next is None else slow. In this case, we are returning the second node
    4. ❗
    Edge Case: What if there are two middle nodes?
def middleNode(head: ListNode) -> ListNode:
        slow = head
        fast = head
        
        while(fast.next and fast.next.next):
            slow = slow.next
            fast = fast.next
            fast = fast.next
        
       
       return slow.next if fast.next is None else slow
image
‣
What are some questions to ask for algorithmic interview problems relating to linked lists?
  1. Is it singly linked? Doubly linked?
  2. How many nodes? Even or odd?
‣
Given a singly linked list, how would you approach iterating backwards on it, in constant space, and without mutating the input?

Reverse the list (or sublist), implement the algorithm, and reverse again.

class Node(object):

    def __init__(self, data = None, node=None):
        # TODO: Implement me
        self.data = data
        self.next = node


    def __str__(self):
        # TODO: Implement me
				return self.data

class LinkedList(object):

    def __init__(self, head=None):
        self.head = head

    def __len__(self):
        curr = self.head
        counter = 0
        while curr is not None:
            counter += 1
            curr = curr.next
        return counter

    def append_to_front(self, data):
        if data is None:
            return None
        node = Node(data, self.head)
        self.head = node
        return node

    def append(self, data):
        if data is None:
            return None
        node = Node(data)
        if self.head is None:
            self.head = node
            return node
        curr_node = self.head
        while curr_node.next is not None:
            curr_node = curr_node.next
        curr_node.next = node
        return node

    def find(self, data):
        if data is None:
            return None
        curr_node = self.head
        while curr_node is not None:
            if curr_node.data == data:
                return curr_node
            curr_node = curr_node.next
        return None

    def delete(self, data):
        if data is None:
            return
        if self.head is None:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        prev_node = self.head
        curr_node = self.head.next
        while curr_node is not None:
            if curr_node.data == data:
                prev_node.next = curr_node.next
                return
            prev_node = curr_node
            curr_node = curr_node.next