chapterLinkedList.tex

% !TEX root = algo-quicksheet.tex
\chapter{Linked List}


\section{Operations}
\subsection{Fundamentals}
Get the $pre$ reference:
\begin{python}
dummy = Node(0)
dummy.next = head
pre = dummy
cur = pre.next
\end{python}

In majority case, we need a reference to pre.

\subsection{Basic Operations}
\begin{enumerate}
\item Get the length
\item Get the $i$-th object
\item Delete a node 
\item Reverse
\begin{figure}[]
\centering
\subfloat{\includegraphics[width=\linewidth]{ll_reverse}}
\caption{Reverse the linked list}
\label{fig:LABEL}
\end{figure}
\begin{python}
def reverseList(self, head):
    dummy = ListNode(0)
    dummy.next = head

    pre = dummy
    cur = head  # ... = dummy.next, not preferred
    while pre and cur:
        assert pre.next == cur
        nxt = cur.next
        # op
        cur.next = pre
        
        pre = cur
        cur = nxt
	
	# original head pointing to dummy
    head.next = None  # dummy.next.next = ..., not preferred
    return pre  # new head
\end{python}
Notice: the evaluation order for the swapping the nodes and links. 
\end{enumerate}

\subsection{Combined Operations}
In $O(n)$ without extra space:
\begin{enumerate}
\item Determine whether two lists intersects
\item Determine whether the list is palindrome 
\item Determine whether the list is acyclic
\end{enumerate}

\section{Combinations}
\subsection{Merge K Linked List}
Given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.
\runinhead{Core Clues:}
\begin{enumerate}
\item Relax the problem: if only two lists, just compare and merge like merge sort 
\item $k$ lists $\Ra$ Heap
\begin{python}
use heap


-------------------
    |  |  |  |  |  |
    |  |  |  |  |  |
    |  |  |  |  |  |
    |  |  |  |  |  |
\end{python}
\end{enumerate}
\begin{python}
def mergeKLists(self, lists):
  h = []
  for node in lists:
    if node:
      heapq.heappush(h, (node.val, node))

  dummy = ListNode(0)
  current = dummy  # verbose name for return
  while h:
    val, mini = heapq.heappop(h)
    current.next = mini
    nxt = mini.next
    if nxt:
      heapq.heappush(h, (nxt.val, nxt))

    current = current.next

  return dummy.next
\end{python}
\subsection{LRU}
Core clues:
\begin{enumerate}
\item Ensure $O(1)$ find $O(1)$ deletion. 
\item Doubly linked list + map.
\item Keep both \pyinline{head} and \pyinline{tail} pointer.
\item Operations on doubly linked list are case by case.  
\end{enumerate}
\begin{python}
class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.pre = None 
        self.next = None


class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}  # key to Node(val)
        self.head = None
        self.tail = None

    def get(self, key):
        if key in self.map:
            cur = self.map[key]
            self._elevate(cur)
            return cur.val

        return -1

    def set(self, key, value):
        if key in self.map:
            cur = self.map[key]
            cur.val = value
            self._elevate(cur)
        else:
            cur = Node(key, value)
            self.map[key] = cur
            self._appendleft(cur)

            if len(self.map) > self.cap:
                last = self._pop()
                del self.map[last.key]

    # doubly linked-list operations only
    def _appendleft(self, cur):
        """Normal or initially empty"""
        if not self.head and not self.tail:
            self.head = cur
            self.tail = cur
            return

        head = self.head
        cur.next, cur.pre = head, None
        head.pre = cur
        self.head = cur

    def _pop(self):
        """Normal or resulting empty"""
        last = self.tail
        if self.head == self.tail:
            self.head, self.tail = None, None
            return last

        pre = last.pre
        pre.next = None
        self.tail = pre
        
        return last

    def _elevate(self, cur):
        """Head, Tail, Middle"""
        pre, nxt = cur.pre, cur.next
        if not pre:
            return
        elif not nxt:
            assert self.tail == cur
            self._pop()
        else:
            pre.next, nxt.pre = nxt, pre

        self._appendleft(cur)
\end{python}

Use \pyinline{OrderedDict}:
\begin{python}
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.kv = OrderedDict()  # key -> value

    def get(self, key: int) -> int | None:
        if key not in self.kv:
            return None  # or raise KeyError
        # Move to MRU position
        self.kv.move_to_end(key, last=False)
        return self.data[key]

    def put(self, key: int, value: int) -> None:
        # If key exists, update value and move to MRU
        if key in self.kv:
            self.kv.move_to_end(key, last=False)
        self.kv[key] = value

        # Evict LRU if over capacity
        if len(self.kv) > self.capacity:
            self.kv.popitem(last=True)   # pop LRU (right side)
\end{python}

\runinhead{First Unique Number in the stream.}

Naive:
\begin{python}
class FirstUnique:
  def __init__(self, A):
    self.cnt = Counter()
    self.q = deque()
    for a in A:
      self.add(a)

  def showFirstUnique(self) -> int:
    while self.q and self.cnt[self.q[0]] > 1:
      # no need to dec counter
      self.q.popleft()
    return self.q[0] if self.q else -1

  def add(self, value: int) -> None:
    self.cnt[value] += 1
    self.q.append(value)
\end{python}

Using Double Linked List:
\begin{python}
from collections import OrderedDict

class FirstUnique:
  def __init__(self, A):
    self.cnt = defaultdict(int)
    self.uniques = OrderedDict()   # Ordered List
    for x in A:
      self.add(x)

  def showFirstUnique(self) -> int:
    return next(iter(self.uniques)) if self.uniques else -1

  def add(self, value):
    self.cnt[value] += 1

    if self.cnt[value] == 1:
      # first time: becomes unique; append to end
      self.uniques[value] = None
    elif self.cnt[value] == 2:
      self.uniques.pop(value, None)
\end{python}

Using Double Linked List without OrderedDict:
\begin{enumerate}
\item Maintain a map: val $\ra$ node if seen once; None if unseen; DUP if seen $\ge$ 2;
\end{enumerate}
\begin{python}
@dataclass
class Node:
  val: int
  prev: Node | None = None
  next: Node | None = None

class DoubleLinkedList:
  def __init__(self):
    self.head = Node(0) 
    self.tail = Node(0)
    self.head.next = self.tail
    self.tail.prev = self.head

  def append(self, node):
    last = self.tail.prev

    node.prev = last
    node.next = self.tail

    last.next = node
    self.tail.prev = node
    return node

  def remove(self, node):
    prev = node.prev
    nxt =  node.next

    prev.next = nxt
    nxt.prev = prev

  def first(self):
    return self.head.next.val \
      if self.head.next is not self.tail else None

DUP = object()

class FirstUnique:
  def __init__(self, A):
    self.dll = DoubleLinkedList()
    # val -> node if seen once; None if unseen; DUP if seen >= 2;
    self.nodes = {}
    for x in A:
      self.add(x)

  def showFirstUnique(self) -> int:
    v = self.dll.first()
    return v if v is not None else -1

  def add(self, value: int):
    if value not in self.nodes:
      node = self.dll.append(Node(value))
      self.nodes[value] = node
    elif self.nodes[value] is not DUP:
      # seen once before
      self.dll.remove(self.nodes[value])
      self.nodes[value] = DUP
    else:
      # DUP 
      pass 
\end{python}