# 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.

- Can also delete a curr node even without a prev pointer: curr.data = curr.next.data; curr.next = curr.next.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

- def hasCycle(self, head):
- 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

- can also use this to detect duplicates in an array given certain constraints
- 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

- https://www.wikiwand.com/en/Cycle_detection#/Tortoise_and_hare
- 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

- def sortList(self, head):

- Sort linked list using O(1) space and O(n log n) time: