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