Linked Lists Problems

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.

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 tail

Typescript solution:

/**
    Recursively reverse the linked list, if it's a single node do nothing.
    @param: list is a Linked List of type ListNode
 
    @return: returns the list but reversed.
 */
function reverseList(list: ListNode): ListNode | null {
    // If a single node in the list
    if(list.next === null || list === null){
        return list;
    }
    // recursively rev the list, call on the rest
    let rest: ListNode = reverseList(list.next);
    // switching the order for the head node
    list.next.next = list;
    list.next = null;
    return rest;
}

Linked 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 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;
    }
}