Merging and summing linkedlists is best done through recursion, finding the correct base-case is paramount, followed by determining the recursive step.
Merging Two LLs based on some condition
merginglinkedlists This done using recursion.
- The base-case is when either is null (empty) then return the head of the other list.
// Handling the sitch where the end of a list is reached, can only return the other one. - The recursive step applies the comparison logic (condition) for the values.
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
if(list1 === null){
return list2;
}
if(list2 === null){
return list1;
}
if(list1.val <= list2.val){
list1.next = mergeTwoLists(list1.next, list2);
return list1;
}
else{
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
};If list1.val <= list2.val: Use the current node from list1 and recursively merge the rest of list1 (i.e., list1.next) with list2. Assign the merged result to list1.next and return list1 as the new head. else do the same but for list2.
This approach continues choosing the node with the smaller value for the next step, until both lists are fully traversed.
Summing Two LLS
sumtwolists is by determining the longest of the two lists and reversing both if the head is the smallest digit.
Iterating through the longer list, if shorter runs out simply count its values as 0, and carrying the carry of each sum. To do this you need to get both the n mod 10 and n / 10 if the sum is greater than 10.
The carry then ends up being a new node (the head) as it forms the largest digit.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function getLength(list: ListNode) : number {
let len: number = 0;
let currentNode: ListNode = list;
while(currentNode != null){
len++;
currentNode = currentNode.next;
}
return len;
}
function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
if(getLength(l1) < getLength(l2)){
// Switch the order of the lists so only handle l1
return addTwoNumbers(l2, l1)
}
let carry: number = 0;
let result = l1; // use the same List because faster than making new one and less space
while(l2 !== null || carry !== 0){
l1.val += carry;
if(l2 !== null){
l1.val += l2.val;
l2 = l2.next;
}
// store int div result and move the carry
carry = Math.floor(l1.val / 10);
l1.val = l1.val % 10;
if(l1.next === null && carry !== 0){
l1.next = new ListNode(0);
}
l1 = l1.next;
}
return result;
}Reverse Linked List - Easy
Another recursion classic, such as classic deserves a tag reverselinkedlist! I recommend drawing this out on paper, because it seems so easy to follow, the only trick is the splitting the list on each cycle.
- Base-case: null node or single node list (node.next is null), return the node.
- Split the LL by recursively calling the function on the tail.
- set the next of the next node to be the current node.
- set the current node to null
- return the tail
Here’s typical Python solution, the Java version is logically identical.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
# Split head from tail
tail = self.reverseList(head.next)
head.next.next = head
head.next = None
return tailLinked List Cycles
Detect a cycle in a linked list, meaning a node points to another using its next ptr causing a cycle (loop).
TWO POOOOINTERS!!!
See LeetCode Patterns > Fast and slow pointer approach
Code:
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null){
return false;
}
ListNode slow = head;
ListNode fast = head;
while(slow != null && fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
// Don't check for values, the ptrs are what matters
if(fast == slow){
return true;
}
}
return false;
}
}LRU Cache - Med
Implement a Least Recently Used lru cache.
The trick is to use a Doubly Linked List with Dummy ends.
Meaning a starting node and ending node that don’t change, makes manipulation easier since the pointers for the ends are constant.
This is also a Hash Tables and Hashmaps problem, because you need to keep record of each key and its corresponding node.
Do NOT forget to remove key-value pairs from the hashmap/dict just as you do from the linked list!
My Python implementation.
class Node:
def __init__(self, key: int, val: int, prev=None, next=None) -> None:
self.key = key
self.val = val
self.prev = prev
self.next = next
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # dict key : node
self.start = Node(0, 0)
self.end = Node(0, 0)
# dummy head and tail that aren't edited make ops easier
self.start.next = self.end
self.end.prev = self.start
def get(self, key: int) -> int:
if key in self.cache:
targt = self.cache[key]
self.remove(targt)
self.insert(targt)
return targt.val
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.remove(self.cache[key])
new_node = Node(key, value)
self.insert(new_node)
self.cache[key] = new_node
if self.capacity < len(self.cache):
rem = self.start.next
self.remove(rem)
del self.cache[rem.key] # del k-v pair from dict
# add at end (before the actual end which is a dummy)
def insert(self, new_node):
tail = self.end.prev
tail.next = new_node
self.end.prev = new_node
new_node.prev = tail
new_node.next = self.end
# rem by unlinking
def remove(self, rem_node):
p = rem_node.prev
n = rem_node.next
p.next = n
n.prev = pWith Python’s OrderedDict:
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key: int) -> int:
if key in self.cache:
targt = self.cache[key]
self.cache.move_to_end(key)
return targt
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if self.capacity < len(self.cache):
self.cache.popitem(last=False)