Linked List（鏈結串列）

# python
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

// java

// Single Linkedlist

public class ListNode{

    // attr
    public int val;
    public ListNode next;

    // constructor
    public ListNode(){

    }

    public ListNode(int val){
        this.val = val;
    }

    ListNode(int val, ListNode next){
        this.val = val;
        this.next = next;
    }

}

// init a ListNode
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);

// motify node's value
node1.val = 0;

// connect nodes
node1.next = node2;
node2.next = node3;

// java

// Double linked list

// LC 146

public class Node {
    int key;
    int val;
    Node prev;
    Node next;

    public Node(int key, int val) {
        this.key = key;
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

def linked_list_operation(head):
    # Create dummy head
    dummy = ListNode(0)
    dummy.next = head

    # Use prev to track previous node
    prev = dummy
    curr = head

    while curr:
        # Perform operations
        if condition:
            # Remove current node
            prev.next = curr.next
        else:
            prev = curr
        curr = curr.next

    # Return new head (dummy.next)
    return dummy.next

fast = slow = head = [1]

Step 1: move fast n=2 steps ahead
  [1] -> [2] -> [3] -> [4] -> [5]
  ^slow          ^fast

Step 2: move both until fast.next is None
  [1] -> [2] -> [3] -> [4] -> [5]
                ^slow          ^fast

Step 3: slow.next = slow.next.next  →  removes [4]
  [1] -> [2] -> [3] -> [5]  ✓

fast = slow = dummy[0]

Step 1: move fast n+1=3 steps ahead
  [0] -> [1] -> [2] -> [3] -> [4] -> [5]
  ^slow                ^fast

Step 2: move both until fast is None
  [0] -> [1] -> [2] -> [3] -> [4] -> [5]
                ^slow                 ^fast → None (stop)

Step 3: slow.next = slow.next.next  →  removes [4]
  [0] -> [1] -> [2] -> [3] -> [5]  → return dummy.next = [1] ✓

fast = slow = head = [1]

Step 1: move fast n=5 steps
  fast: 1 -> 2 -> 3 -> 4 -> 5 -> None

  [1] -> [2] -> [3] -> [4] -> [5] -> None
  ^slow                               ^fast (None!)

Step 2: while fast.next → fast is None, loop NEVER runs
  slow is still at [1]  (the head itself!)

Step 3: slow.next = slow.next.next
  → This removes [2], NOT the head — WRONG ❌

  Must add a special case:
  if not fast:
      return head.next  # ← extra branch needed

fast = slow = dummy[0]

Step 1: move fast n+1=6 steps ahead
  fast: dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None

  [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> None
  ^slow                                       ^fast (None)

Step 2: while fast → fast is None, loop NEVER runs
  slow stays at dummy[0]  ← one node BEFORE the head

Step 3: slow.next = slow.next.next
  dummy.next = [2]  →  head [1] is removed ✓

Return dummy.next = [2] -> [3] -> [4] -> [5]  ✓  No special case!

# LC 19 — with dummy (handles all cases cleanly)
def removeNthFromEnd(self, head, n):
    dummy = ListNode(0)
    dummy.next = head
    fast = slow = dummy

    for _ in range(n + 1):   # fast moves n+1 steps
        fast = fast.next

    while fast:               # move both until fast is None
        fast = fast.next
        slow = slow.next

    slow.next = slow.next.next   # remove the target node
    return dummy.next

def deleteDuplicates(self, head):
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

    while head and head.next:
        if head.val == head.next.val:
            # Skip all duplicates
            val = head.val
            while head and head.val == val:
                head = head.next
            prev.next = head
        else:
            prev = head
            head = head.next

    return dummy.next

def partition(self, head, x):
    before_dummy = ListNode(0)
    after_dummy = ListNode(0)
    before = before_dummy
    after = after_dummy

    while head:
        if head.val < x:
            before.next = head
            before = before.next
        else:
            after.next = head
            after = after.next
        head = head.next

    # Connect the two parts
    after.next = None
    before.next = after_dummy.next
    return before_dummy.next

// Java
public ListNode removeElements(ListNode head, int val) {
    // 1. Create dummy node pointing to head
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    // 2. Use curr pointer (starts at dummy, looks ahead)
    ListNode curr = dummy;

    // 3. Look ahead at NEXT node
    while (curr.next != null) {
        if (curr.next.val == val) {
            // Found match - skip the next node
            // NOTE: curr does NOT move!
            curr.next = curr.next.next;
        } else {
            // No match - move pointer forward
            curr = curr.next;
        }
    }

    // 4. Return actual head
    return dummy.next;
}

# Python
def removeElements(self, head: ListNode, val: int) -> ListNode:
    dummy = ListNode(0)
    dummy.next = head
    curr = dummy

    while curr.next:
        if curr.next.val == val:
            curr.next = curr.next.next  # skip, don't move curr
        else:
            curr = curr.next  # move forward

    return dummy.next

Initial: dummy -> 6 -> 6 -> 6 -> 3, curr at dummy

Step 1: curr.next.val = 6 (match!)
  Action: curr.next = curr.next.next
  Result: dummy -> 6 -> 6 -> 3 (curr STAYS at dummy)

Step 2: curr.next.val = 6 (match!)
  Action: curr.next = curr.next.next
  Result: dummy -> 6 -> 3 (curr STAYS at dummy)

Step 3: curr.next.val = 6 (match!)
  Action: curr.next = curr.next.next
  Result: dummy -> 3 (curr STAYS at dummy)

Step 4: curr.next.val = 3 (no match)
  Action: curr = curr.next
  Result: curr moves to node 3

Step 5: curr.next = null, exit loop
Return: dummy.next = [3]

head(dummy) <-> [LRU] <-> ... <-> [MRU] <-> tail(dummy)

# python
# LC 146 - LRU Cache
class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> Node

        # sentinel boundaries: head <-> ... <-> tail
        self.head = Node(0, 0)  # LRU side
        self.tail = Node(0, 0)  # MRU side
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def _insert(self, node):          # insert just before tail (MRU)
        prev = self.tail.prev
        prev.next  = node
        node.prev  = prev
        node.next  = self.tail
        self.tail.prev = node

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._insert(node)            # move to MRU
        return node.val

    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._insert(node)        # refresh to MRU
            return

        if len(self.cache) == self.capacity:
            lru = self.head.next      # evict LRU (closest to head)
            self._remove(lru)
            del self.cache[lru.key]

        node = Node(key, value)
        self.cache[key] = node
        self._insert(node)

put(1,1): head <-> [1] <-> tail
put(2,2): head <-> [1] <-> [2] <-> tail
get(1):   head <-> [2] <-> [1] <-> tail   ← 1 moved to MRU
put(3,3): evict head.next=[2]
          head <-> [1] <-> [3] <-> tail

# python — reusable helper: reverse k nodes starting at `head`
# time = O(k), space = O(1)
def reverse_helper(self, head, k):
    prev = None
    curr = head

    while curr and k > 0:
        nxt = curr.next     # 1) cache next
        curr.next = prev    # 2) reverse the link
        prev = curr         # 3) advance prev
        curr = nxt          # 4) advance curr
        k -= 1

    # prev = new head of reversed list   (was the k-th node)
    # head = new tail  (original head, now points forward to `curr`)
    # curr = first node AFTER the reversed segment
    return prev, head, curr

# python
# LC 92 - reverse nodes from position `left` to `right`
# time = O(n), space = O(1)
class Solution(object):
    def reverseBetween(self, head, left, right):
        # edge case
        if not head or left == right:
            return head

        dummy = ListNode(0)
        dummy.next = head

        # 1) walk `prev` to the node BEFORE position `left`
        prev = dummy
        for _ in range(left - 1):
            prev = prev.next

        # 2) `start` = first node of the segment to reverse
        start = prev.next

        # 3) reverse (right - left + 1) nodes via the helper
        new_head, new_tail, next_node = self.reverse_helper(
            start, right - left + 1
        )

        # 4) reconnect both boundaries
        prev.next = new_head       # front:  prev -> new head of reversed chunk
        new_tail.next = next_node  # back:   old head (now tail) -> rest of list

        return dummy.next

    def reverse_helper(self, head, k):
        prev = None
        curr = head
        while curr and k > 0:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
            k -= 1
        return prev, head, curr

dummy -> 1 -> 2 -> 3 -> 4 -> 5
              └──── reverse these 3 ────┘

Step 1) walk prev (left-1 = 1 step) to node before segment
   dummy -> 1 -> 2 -> 3 -> 4 -> 5
            ^prev  ^start
                   (start = prev.next = node 2)

Step 2) reverse_helper(start=2, k=3)
   -- reverses links of 2,3,4 in isolation --
   before:   2 -> 3 -> 4 -> 5
   after:    2 <- 3 <- 4      5
             |              |
          new_tail       new_head
   returns:
     new_head  = 4   (was k-th node, now front of chunk)
     new_tail  = 2   (was `start`, now points nowhere yet)
     next_node = 5   (first node after the reversed part)

Step 3) reconnect boundaries
   (C1) prev.next = new_head
        node1.next -> 4
   (C2) new_tail.next = next_node
        node2.next -> 5

Final:
   dummy -> 1 -> 4 -> 3 -> 2 -> 5
                 └── reversed ──┘
   return dummy.next  =>  [1, 4, 3, 2, 5]  ✓

        prev        new_head → ... → new_tail        next_node
          |             |                 |               |
   ... -> 1             4 -> 3 -> 2         (dangling)      5 -> ...
          |_____________|                 |_______________|
             (C1) prev.next = new_head        (C2) new_tail.next = next_node

# python
# LC 25 - reverse every k nodes; leave the tail (< k) as-is
# time = O(n), space = O(1)
class Solution(object):
    def reverseKGroup(self, head, k):
        # count if >= k nodes remain
        def has_k(node, k):
            cnt = 0
            while node and cnt < k:
                node = node.next
                cnt += 1
            return cnt == k

        dummy = ListNode(0)
        dummy.next = head
        prev = dummy               # node before current group

        while has_k(prev.next, k):
            start = prev.next
            new_head, new_tail, next_node = self.reverse_helper(start, k)
            prev.next = new_head        # front of group
            new_tail.next = next_node   # tail of group -> rest
            prev = new_tail             # move `prev` to end of this group
        return dummy.next

    def reverse_helper(self, head, k):
        prev = None
        curr = head
        while curr and k > 0:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
            k -= 1
        return prev, head, curr

// java
// single Linklist
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

# python
class Node:
  """
  # constructor
  # A single node of a singly linked list
  """
  def __init__(self, data=None, next=None): 
    self.data = data
    self.next = next

class LinkedList:
  """
  # A Linked List class with a single head node
  """
  def __init__(self):  
    self.head = Node()

  def get_length(self):
    """
    # get list length method for the linked list
    i.e. 
       before : 1 -> 2 -> 3
       after  : 3
    """
    current = self.head
    length = 0 
    while current:
        current = current.next
        length += 1 
    return length

  def get_tail(self):
    """
    # get list tail method for the linked list
    i.e. 
       before : a -> b -> c
       after  : c
    """
    current = self.head
    while current:
        current = current.next
    return current

  def print(self):
    """
    # print method for the linked list
    i.e. 
       before : 1 -> 2 -> 3
       after  : 1 2 3 
    """
    current = self.head
    while current:
      print (current.data)
      current = current.next

  def append(self, data):
    """
    # append method that append a new item at the end of the linkedlist 
    i.e. 
         before :  1 -> 2 -> 3
         after  :  1 -> 2 -> 3 -> 4
    """
    newNode = Node(data)
    if self.head:
      current = self.head
      while current.next:
        current = current.next
      current.next = newNode
    else:
      self.head = newNode
  
  def prepend(self, data):
    """
    # append method that append a new item at the head of the linkedlist 
    i.e. 
         before :  1 -> 2 -> 3
         after  :  0 -> 1 -> 2 -> 3
    """
    newNode = Node(data)
    if self.head:
        current = self.head
        self.head = newNode
        newNode.next = current
        current = current.next
    else:
        self.head = newNode

  def insert(self, idx, data):
    """
    # append method that append a new item within the linkedlist 
    i.e. 
         before :  1 -> 2 -> 3
         insert(1, 2.5)
         after  :  1 -> 2 -> 2.5 -> 3
         before :  1 -> 2 -> 3
         insert(0, 0)
         after  :  0 -> 1 -> 2 -> 3
         before :  1 -> 2 -> 3
         insert(2, 4)
         after  :  1 -> 2 -> 3 -> 4
    """
    current = self.head
    ll_length = self.get_length()

    if idx < 0 or idx > self.get_length():
      print ("idx out of linkedlist range, idx : {}".format(idx))
      return
    elif idx == 0:
        self.prepend(data)
    elif idx == ll_length:
        self.append(data)
    else:
        newNode = Node(data)
        current = self.head
        cur_idx = 0 
        while cur_idx < idx-1:
            current = current.next
            cur_idx += 1 
        newNode.next = current.next
        current.next = newNode

  def remove(self, idx):
    """
    # remove method for the linked list
    i.e. 
       before : 1 -> 2 -> 3
       remove(1) 
       after  : 1 -> 3
       before : 1 -> 2 -> 3
       remove(2) 
       after  : 1 -> 2
       before : 1 -> 2 -> 3
       remove(0) 
       after  : 2 -> 3
    """
    if idx < 0 or idx > self.get_length():
        print ("idx out of linkedlist range, idx : {}".format(idx))
        return 
    elif idx == 0:
        current = self.head
        self.head = current.next
    elif idx == self.get_length():
        current = self.head
        cur_idx = 0
        while cur_idx < idx -1:
            current = current.next
            cur_idx += 1
        current.next = None
    else:
        current = self.head
        cur_idx = 0 
        while cur_idx < idx - 1:
            current = current.next
            cur_idx += 1 
        next_ = current.next.next
        current.next = next_
        current = next_ 

  def reverse(self): 
    """
    https://www.youtube.com/watch?v=D7y_hoT_YZI

    # reverse method for the linked list
    # https://www.geeksforgeeks.org/python-program-for-reverse-a-linked-list/
    i.e. 
     before : 1 -> 2 -> 3
     after  : 3 -> 2 -> 1 
    """
    prev = None
    current = self.head 
    while(current is not None): 
        next_ = current.next
        current.next = prev 
        prev = current 
        current = next_
    self.head = prev 

# python
#-------------------------
# iteration
#-------------------------
# LC 206

# V0
# IDEA : Linkedlist basics
# https://www.youtube.com/watch?v=D7y_hoT_YZI
# STEPS)
# -> STEP 1) cache "next"
# -> STEP 2) point head.next to prev
# -> STEP 3) move prev to head
# -> STEP 4) move head to "next"
class Solution(object):
    def reverseList(self, head):
        # edge case
        if not head:
            return
        prev = None
        while head:
            # cache "next"
            tmp = head.next
            # point head.next to prev
            head.next = prev
            # move prev to head (for next iteration)
            prev = head
            # move head to "next" (for next iteration)
            head = tmp
        # NOTE!!! we return prev
        return prev

// java
//---------------------------
// iteration
//---------------------------
// LC 206
// V0
public ListNode reverseList(ListNode head) {

    if (head == null) {
        return null;
    }

    ListNode _prev = null;

    while (head != null) {
        /**
         *  NOTE !!!!
         *
         *   4 operations
         *
         *    step 1) cache next
         *    step 2) point cur to prev
         *    step 3) move prev to cur
         *    step 4) move cur to next
         *
         */
        ListNode _next = head.next;
        head.next = _prev;
        _prev = head;
        head = _next;
    }

    // NOTE!!! we return _prev here, since it's now "new head"
    return _prev;

}

// java
//---------------------------
// recursion
//---------------------------
// LC 206
// algorithm book (labu) p.290
// IDEA: recurse to the tail, then let each frame flip the link BEHIND it on the way back.
//       `newHead` is the original last node and is passed up unchanged.
// time = O(n), space = O(n)   (call stack)
ListNode reverseList(ListNode head) {
    // base case: empty list, or already at the last node
    if (head == null || head.next == null) {
        return head;
    }

    // reverse everything after `head`; newHead is the tail of the ORIGINAL list
    ListNode newHead = reverseList(head.next);

    /** NOTE !!!
     *
     *  head.next is the node that now sits BEHIND head in the reversed list,
     *  so pointing it back at head is the whole flip.
     */
    head.next.next = head;
    // cut the old forward link, or the two nodes form a 2-cycle
    head.next = null;

    return newHead;
}

// java
//---------------------------
// iteration
//---------------------------
// algorithm book (labu) p.298
ListNode reverse(ListNode a, Listnode b){
    ListNode pre, cur, nxt;
    pre = null;
    cur = a;
    nxt = a;
    /** THE ONLY DIFFERENCE (reverse nodes VS reverse nodes in [a,b]) */
    while (cur != b){
        nxt = cur.next;
        // reverse on each node
        cur.next = pre;
        // update pointer
        pre = cur;
        cur = nxt;
    }

    // return reversed nodes
    return pre;
}

// java
//---------------------------
// iteration
//---------------------------
// LC 25
// algorithm book (labu) p.298
/** NOTE !!! `reverse(a, b)` is exactly the primitive from 1-1-3) above — reverse the
 *  half-open interval [a, b) and return its new head. Reproduced there, not here. */
ListNode reverseKGroup(ListNode head, int k){
    if (head == null) return null;
    // inverval [a,b] has k to-reverse elements
    ListNode a, b;
    a = b = head;
    for (int i = 0; i < k; i++){
        // not enough elements (amount < k), no need to reverse -> base case
        if (b == null) return head;
        b = b.next;
    }
    // reverse k elements
    ListNode newHead = reverse(a,b);
    // reverse remaining nodes, and connect with head
    a.next = reverseKGroup(b,k);
    return newHead;
}

# LC 025
class Solution:
    def reverseKGroup(self, head, k):
        # help func
        # check if # of sub nodes still > k
        def check(head, k):
            ans = 0
            while head:
                ans += 1
                if ans >= k:
                    return True
                head = head.next
            return False

        # edge case
        if not head:
            return
        d = dummy = ListNode(None)
        pre = None
        preHead = curHead = head
        while check(curHead, k):
            for _ in range(k):
                # reverse linked list
                tmp = curHead.next
                curHead.next = pre
                pre = curHead
                curHead = tmp
            # reverse linked list
            # ???
            dummy.next = pre
            dummy = preHead
            preHead.next = curHead
            preHead = curHead
        return d.next

//---------------------------
// recursion
//---------------------------
// java
// algorithm book (labu) p.293

// "postorder" node
ListNode successor = null;

// reverse first N node (from head), and return new head
ListNode reverseN(ListNode head, int n){
    if (n == 1){
        // record n + 1 nodes, will be used in following steps
        successor = head.next;
        return head;
    }

    // set head.next as start point, return first n - 1 nodes
    ListNode last = reverseN(head.next, n-1);

    head.next.next = head;
    // connect reversed head node and following nodes
    head.next = successor;
    return last;
}

// java
//---------------------------
// recursion
//---------------------------
// algorithm book (labu) p.293

/** NOTE !!! `reverseN` is the primitive from 1-1-5) above, unchanged. Only the
 *  `reverseBetween` wrapper below is new: walk m down to 1, then reverse the first n. */
// reverse nodes in index = m to index = n
ListNode reverseBetween(ListNode head, int m, int n){
    // base case
    if (m == 1){
        return reverseN(head, n);
    }

    // for head.next, the op is reverse interval : [m-1, n-1]
    // will trigger base case when when meet reverse start point
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

# LC 002
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        NOTE :
         1. we init linkedlist via ListNode()
         2. we NEED make extra head refer same linkedlist, since we need to return beginning of linkedlist of this func, while res will meet "tail" at the end of while loop
        """
        head = res = ListNode()
        plus = 0
        tmp = 0
        while l1 or l2:
            tmp += plus
            plus = 0
            if l1:
                tmp += l1.val
                l1 = l1.next
            if l2:
                tmp += l2.val
                l2 = l2.next
            if tmp > 9:
                tmp -= 10
                plus = 1

            res.next = ListNode(tmp)
            res = res.next
            tmp = 0
        ### NOTE : need to deal with case : l1, l2 are completed, but still "remaining" plus
        if plus != 0:
            res.next = ListNode(plus)
            res = res.next
        #print ("res = " + str(res))
        #print ("head = " + str(head))
        return head.next

# LC 445 Add Two Numbers II
# V0
# IDEA : string + linked list
# DEMO
# input :
# [7,2,4,3]
# [5,6,4]
# intermedia output : 
# l1_num = 7243
# l2_num = 564
class Solution:
    def addTwoNumbers(self, l1, l2):
        if not l1 and not l2:
            return None

        l1_num = 0
        while l1:
            l1_num = l1_num * 10 + l1.val
            l1 = l1.next

        l2_num = 0
        while l2:
            l2_num = l2_num * 10 + l2.val
            l2 = l2.next

        print ("l1_num = " + str(l1_num))
        print ("l2_num = " + str(l2_num))


        ### NOTE : trick here :
        #    -> get int format of 2 linked list first (l1, l2)
        #    -> then sum them (l1_num + l2_num)
        lsum = l1_num + l2_num

        head = ListNode(None)
        cur = head
        ### NOTE : go thrpigh the linked list int sum, append each digit to ListNode and return it
        for istr in str(lsum):
            cur.next = ListNode(int(istr))
            cur = cur.next
        # NOTE : need to return head (but not cur, since cur already meet the end of ListNode)
        return head.next

// algorithm book p. 286
// java
Listnode slow, fast;
slow = fast = head;
while (fast && fast.next){
    fast = fast.next.next;
    slow = slow.next;
}
// slow pointer will be linked list middle point

// if element count in linked list is odd (TO VERIFY)
if (fast != null){
    slow = slow.next;
}

# LC 876 Middle of the Linked List
# V0
# IDEA : fast, slow pointers + linkedlist
class Solution(object):
    def middleNode(self, head):
        # edge case
        if not head:
            return
        s = f = head
        while f and f.next:
            # if not f:
            #     break
            f = f.next.next
            s = s.next
        return s