4)Linked Lists:

Linked Lists:

  • All a linked list really is is the head node (which points to the next node, and so on).
  • To reverse a linked list, just need to remember to store next and update prev and curr pointers at each iteration:
    • nxt = curr.next
    • curr.next = prev
    • prev = curr
    • curr = nxt
  • To recursively reverse:
    • base case is null node or null node.next
    • remember to set head.next.next to head and then head.next = None
  • Deleting a node n is just setting the references to skip n: prev.next = n.next;
    • Can also delete a curr node even without a prev pointer: curr.data = curr.next.data; curr.next = curr.next.next;
      Basically, copy (and overwrite) next's data to curr and delete next.
  • Just make sure to check for the null pointer (!!) and be aware of the head pointer.
  • Linked lists offer easy modification but non-existent random access.
  • An important technique is the "runner" one:
    • Have two pointers iterating through the list, with one pointer either ahead by a fixed amount or actually moving faster.
    • For example, to determine the midpoint of a linked list, have two pointers such that one of them jumps 2 nodes at once and the other just 1. When the fast pointer hits the end, the slow one will be in the middle of the list.
    • To determine if a linked list has a cycle, do the same thing where 1 pointer moves ahead 2 nodes at a time. If there's a cycle, the runner will eventually equal the normal curr node. If not, will hit null node.
      • https://www.wikiwand.com/en/Cycle_detection#/Tortoise_and_hare
        • def hasCycle(self, head):
          • slow = fast = head
          • while fast and fast.next:
            • slow = slow.next
            • fast = fast.next.next
            • if slow == fast: return True
          • return False
      • then, once fast = slow, reset slow to head of list, and move forward both pointers 1 at a time. once they equal again, that's the start of the cycle. then move the fast pointer 1 at a time, once they equal for the 3rd time, that's the length of the cycle
        • can also use this to detect duplicates in an array given certain constraints
          • http://keithschwarz.com/interesting/code/?dir=find-duplicate
          • https://leetcode.com/problems/find-the-duplicate-number/description/
        • def detectCycle(self, head):
          • slow = fast = head
          • has_cycle = False
          • while fast and fast.next:
            • slow = slow.next
            • fast = fast.next.next
            • if slow == fast:
              • has_cycle = True
              • break
          • if not has_cycle: return None
          • # the point where they meet again, resetting slow to head, is the cycle start
          • while head != fast:
            • head = head.next
            • fast = fast.next
          • return head
      • or alternatively, if don't need the start index and just want cycle length, move fast 1 node at a time until hits slow again
    • A fixed amount (also called the stick approach) use case would be to determine the start of a cycle if you know the length of the cycle.
  • Recursion can often help.
  • Example problems and model code:
    • Sort linked list using O(1) space and O(n log n) time:
      https://leetcode.com/problems/sort-list/description/
      • def sortList(self, head):
        • # base case
        • if not head or not head.next: return head
        • # get middle (if even, get 1st middle)
        • slow = fast = head
        • while fast.next and fast.next.next:
          • slow = slow.next
          • fast = fast.next.next
        • # split list in two and sort halves
        • h2 = slow.next
        • slow.next = None
        • left = self.sortList(head)
        • right = self.sortList(h2)
        • # then merge sorted halves
        • return self.merge_sorted_lists(left, right)
      • def merge_sorted_lists(self, h1, h2):
        • if None in (h1, h2): return h1 or h2
        • if h1.val <= h2.val:
          • h1.next = self.merge_sorted_lists(h1.next, h2)
          • return h1
        • else:
          • h2.next = self.merge_sorted_lists(h1, h2.next)
          • return h2
darkmode