Linked List problems

Problem 1: Linked List Cycle

Explanation:

Given a linked list, determine if it has a cycle in it.

Approach:

1. Floyd’s Cycle Detection Algorithm:
   • Use two pointers, slow and fast.
   • Move slow by one step and fast by two steps.
   • If they meet, there is a cycle; otherwise, if fast reaches null, there is no cycle.

Time & Space Complexity:

• Time Complexity: O(n), since each node is visited at most once.
• Space Complexity: O(1), as only two pointers are used.

Java Implementation:

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class LinkedListCycle {
    /**
     * Detects if a linked list contains a cycle.
     * @param head - head node of the linked list
     * @return true if cycle exists, false otherwise
     */
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
    
    public static void main(String[] args) {
        ListNode head = new ListNode(3);
        head.next = new ListNode(2);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(-4);
        head.next.next.next.next = head.next; // Creating cycle
        
        System.out.println("Output: " + hasCycle(head));
    }
}

Example:

Input:

head = [3,2,0,-4], where -4 points to 2

Output:

true

Edge Cases Considered:

• Empty list → Should return false.
• Single node pointing to itself → Should return true.
• List with multiple nodes but no cycle → Should return false.

---

Problem 2: Intersection of Two Linked Lists

Explanation:

Given the heads of two singly linked lists, return the node where the two lists intersect, or null if they do not intersect.

Approach:

1. Two Pointer Technique:
   • Traverse both lists and calculate their lengths.
   • Align the starting position of the longer list.
   • Traverse both lists together until they meet or reach the end.

Time & Space Complexity:

• Time Complexity: O(m + n), where m and n are the lengths of the lists.
• Space Complexity: O(1), as only two pointers are used.

Java Implementation:

public class IntersectionTwoLinkedLists {
    /**
     * Finds the intersection node of two linked lists.
     * @param headA - head of the first linked list
     * @param headB - head of the second linked list
     * @return intersection node or null if no intersection exists
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        
        ListNode a = headA, b = headB;
        while (a != b) {
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }
        return a;
    }
    
    public static void main(String[] args) {
        ListNode headA = new ListNode(4);
        headA.next = new ListNode(1);
        ListNode headB = new ListNode(5);
        headB.next = new ListNode(6);
        headB.next.next = new ListNode(1);
        ListNode intersection = new ListNode(8);
        headA.next.next = intersection;
        headB.next.next.next = intersection;
        intersection.next = new ListNode(4);
        intersection.next.next = new ListNode(5);
        
        System.out.println("Output: " + getIntersectionNode(headA, headB).val);
    }
}

Example:

Input:

List A = [4,1,8,4,5]
List B = [5,6,1,8,4,5]
Intersection at node with value = 8

Output:

8

Edge Cases Considered:

• No intersection → Should return null.
• Lists of different lengths but intersecting → Should return the correct intersection node.
• Lists with only one node each and they intersect → Should return that node.

---

Problem 3: Remove Linked List Elements

Explanation:

Given the head of a linked list and an integer val, remove all the nodes of the linked list that have val.

Approach:

1. Dummy Node Technique:
   • Use a dummy node before head to handle cases where head needs to be removed.
   • Iterate through the list and remove nodes with val.

Time & Space Complexity:

• Time Complexity: O(n), since each node is visited once.
• Space Complexity: O(1), as no extra space is used.

Java Implementation:

public class RemoveLinkedListElements {
    /**
     * Removes elements with a given value from a linked list.
     * @param head - head node of the linked list
     * @param val - value to remove
     * @return new head of the linked list
     */
    public static ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;
        
        while (current.next != null) {
            if (current.next.val == val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        return dummy.next;
    }
    
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(6);
        head.next.next.next = new ListNode(3);
        head.next.next.next.next = new ListNode(4);
        head.next.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next.next = new ListNode(6);
        
        ListNode result = removeElements(head, 6);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

Example:

Input:

head = [1,2,6,3,4,5,6], val = 6

Output:

1 2 3 4 5

Edge Cases Considered:

• All nodes contain val → Should return null.
• No nodes contain val → List remains unchanged.
• Only the last node contains val → Should remove the last node correctly.

---

Problem 4: Reverse Linked List

Explanation:

Given the head of a singly linked list, reverse the list and return the new head.

Approach:

1. Iterative Approach:
   • Maintain three pointers: prev, current, and next.
   • Traverse the list and reverse the next pointers.
2. Recursive Approach (Alternative): Recursively reverse the list.

Time & Space Complexity:

• Time Complexity: O(n), since each node is visited once.
• Space Complexity: O(1), as no extra space is used.

Java Implementation:

public class ReverseLinkedList {
    /**
     * Reverses a linked list.
     * @param head - head node of the linked list
     * @return new head of reversed list
     */
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        while (current != null) {
            ListNode next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }
    
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        
        ListNode result = reverseList(head);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

Example:

Input:

head = [1,2,3,4,5]

Output:

5 4 3 2 1

Edge Cases Considered:

• Single node list → Should return the same node.
• Empty list → Should return null.
• List with multiple nodes → Should reverse all links.

---

Problem 5: Palindrome Linked List

Explanation:

Given the head of a singly linked list, determine if it is a palindrome.

Approach:

1. Find the Middle of the List: Use the slow and fast pointer technique.
2. Reverse the Second Half: Reverse the second half of the linked list.
3. Compare Both Halves: Check if the first half matches the reversed second half.

Time & Space Complexity:

• Time Complexity: O(n), since we traverse the list multiple times.
• Space Complexity: O(1), since we reverse in place.

Java Implementation:

public class PalindromeLinkedList {
    /**
     * Checks if a linked list is a palindrome.
     * @param head - head node of the linked list
     * @return true if palindrome, false otherwise
     */
    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode reversedSecondHalf = reverse(slow);
        ListNode firstHalf = head;
        
        while (reversedSecondHalf != null) {
            if (firstHalf.val != reversedSecondHalf.val) return false;
            firstHalf = firstHalf.next;
            reversedSecondHalf = reversedSecondHalf.next;
        }
        return true;
    }
    
    private static ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
    
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(1);
        
        System.out.println("Output: " + isPalindrome(head));
    }
}

Example:

Input:

head = [1,2,2,1]

Output:

true

Edge Cases Considered:

• Single node list → Should return true.
• Even-length palindrome → Should return true.
• Odd-length palindrome → Should return true.
• Not a palindrome → Should return false.

---

Problem 6: Reverse Linked List II

Explanation:

Reverse a sublist of a linked list from position left to right.

Approach:

1. Find the left boundary: Traverse to left - 1 node.
2. Reverse the sublist: Reverse the nodes from left to right.
3. Reattach the reversed sublist: Connect it back to the list.

Time & Space Complexity:

• Time Complexity: O(n), since we traverse the list once.
• Space Complexity: O(1), since we modify in place.

Java Implementation:

public class ReverseLinkedListII {
    /**
     * Reverses a sublist of a linked list.
     * @param head - head node of the linked list
     * @param left - starting position
     * @param right - ending position
     * @return modified head of the linked list
     */
    public static ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || left == right) return head;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        
        for (int i = 1; i < left; i++) prev = prev.next;
        ListNode start = prev.next;
        ListNode then = start.next;
        
        for (int i = 0; i < right - left; i++) {
            start.next = then.next;
            then.next = prev.next;
            prev.next = then;
            then = start.next;
        }
        return dummy.next;
    }
    
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        
        ListNode result = reverseBetween(head, 2, 4);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

Example:

Input:

head = [1,2,3,4,5], left = 2, right = 4

Output:

1 4 3 2 5

Edge Cases Considered:

• Reversing entire list → Should work correctly.
• Single node list → Should return the same node.
• Reversing at the head → Should correctly update head.

---

Problem 7: Copy List with Random Pointer

Explanation:

A linked list is given where each node contains an additional pointer random, which may point to any node in the list or null. Return a deep copy of the list.

Approach:

1. Interweaving Nodes: Insert new copied nodes next to the original nodes.
2. Assign Random Pointers: Copy the random pointers from the original list to the copied list.
3. Separate Lists: Extract the copied list from the original one.

Time & Space Complexity:

• Time Complexity: O(n), since we traverse the list multiple times.
• Space Complexity: O(1), as we modify the list in place.

Java Implementation:

class Node {
    int val;
    Node next, random;
    Node(int val) {
        this.val = val;
        this.next = this.random = null;
    }
}

public class CopyListWithRandomPointer {
    /**
     * Creates a deep copy of a linked list with random pointers.
     * @param head - head node of the linked list
     * @return new head of the copied list
     */
    public static Node copyRandomList(Node head) {
        if (head == null) return null;
        
        Node curr = head;
        while (curr != null) {
            Node temp = new Node(curr.val);
            temp.next = curr.next;
            curr.next = temp;
            curr = temp.next;
        }
        
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }
        
        Node newHead = head.next, copy = newHead;
        curr = head;
        while (curr != null) {
            curr.next = curr.next.next;
            if (copy.next != null) copy.next = copy.next.next;
            curr = curr.next;
            copy = copy.next;
        }
        return newHead;
    }
    
    public static void main(String[] args) {
        Node head = new Node(7);
        head.next = new Node(13);
        head.next.random = head;
        head.next.next = new Node(11);
        head.next.next.random = head.next.next;
        head.next.next.next = new Node(10);
        head.next.next.next.random = head.next;
        head.next.next.next.next = new Node(1);
        head.next.next.next.next.random = head;
        
        Node copiedHead = copyRandomList(head);
        System.out.println("Copied list created.");
    }
}

Example:

Input:

head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

Output:

Deep copied list with the same structure.

Edge Cases Considered:

• List with no random pointers → Should correctly copy next pointers.
• List where all nodes point to a single node → Should maintain correct references.
• Single-node list → Should return a copy with the same value.

---

Problem 8: Remove Nth Node From End of List

Explanation:

Given the head of a linked list, remove the nth node from the end and return its head.

Approach:

1. Two-Pointer Technique:
   • Move fast pointer n steps ahead.
   • Move both slow and fast until fast reaches the end.
   • Remove the slow.next node.

Time & Space Complexity:

• Time Complexity: O(n), since we traverse the list once.
• Space Complexity: O(1), as only two pointers are used.

Java Implementation:

public class RemoveNthNodeFromEnd {
    /**
     * Removes the nth node from the end of the list.
     * @param head - head node of the linked list
     * @param n - position from the end to remove
     * @return new head of the linked list
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy, fast = dummy;
        
        for (int i = 0; i <= n; i++) fast = fast.next;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
    
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        
        ListNode result = removeNthFromEnd(head, 2);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

Example:

Input:

head = [1,2,3,4,5], n = 2

Output:

1 2 3 5

Edge Cases Considered:

• Removing the first node → Should correctly update head.
• Removing the last node → Should correctly handle tail removal.
• Single-node list → Should return null.

---

Problem 9: LRU Cache

Explanation:

Implement an LRU (Least Recently Used) Cache with get and put operations in O(1) time complexity.

Approach:

1. HashMap for O(1) Lookup: Store key-value pairs.
2. Doubly Linked List for LRU Management:
   • Move recently accessed nodes to the front.
   • Remove the least recently used node when capacity is exceeded.

Time & Space Complexity:

• Time Complexity: O(1) for get and put.
• Space Complexity: O(capacity), since we store up to capacity elements.

Java Implementation:

import java.util.*;

class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> cache;
    private final Node head, tail;
    
    private static class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        Node node = cache.get(key);
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            if (cache.size() == capacity) removeLRU();
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
        }
    }
    
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
    
    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
    
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private void removeLRU() {
        Node lru = tail.prev;
        removeNode(lru);
        cache.remove(lru.key);
    }
    
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println("Output: " + cache.get(1)); // Returns 1
        cache.put(3, 3);
        System.out.println("Output: " + cache.get(2)); // Returns -1 (removed due to LRU policy)
    }
}

Example:

Input:

LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);
cache.put(3, 3);
cache.get(2);

Output:

1
-1

Edge Cases Considered:

• Capacity of 1 → Should evict the only stored item correctly.
• Multiple accesses to the same key → Should update position correctly.
• Eviction order handling → Ensures the least recently used item is removed.

---

Problem 10: Merge k Sorted Lists

Explanation:

Given an array of k linked lists, each sorted in ascending order, merge all the lists into one sorted linked list.

Approach:

1. Min-Heap (Priority Queue) Approach:
   • Use a priority queue to always extract the smallest element from the k lists.
   • Add the extracted node’s next node back into the priority queue.
2. Iterate Until All Nodes are Merged: Keep popping and pushing nodes until the queue is empty.

Time & Space Complexity:

• Time Complexity: O(n log k), where n is the total number of nodes.
• Space Complexity: O(k), used for the priority queue.

Java Implementation:

import java.util.PriorityQueue;

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

public class MergeKSortedLists {
    /**
     * Merges k sorted linked lists into a single sorted list.
     * @param lists - array of linked lists
     * @return merged sorted linked list
     */
    public static ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode node : lists) {
            if (node != null) pq.add(node);
        }
        
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        while (!pq.isEmpty()) {
            ListNode minNode = pq.poll();
            current.next = minNode;
            current = current.next;
            if (minNode.next != null) pq.add(minNode.next);
        }
        return dummy.next;
    }
    
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(5);
        
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);
        
        ListNode l3 = new ListNode(2);
        l3.next = new ListNode(6);
        
        ListNode[] lists = {l1, l2, l3};
        ListNode result = mergeKLists(lists);
        
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

Example:

Input:

lists = [[1,4,5],[1,3,4],[2,6]]

Output:

1 1 2 3 4 4 5 6

Edge Cases Considered:

• All lists are empty → Should return null.
• One non-empty list → Should return that list as is.
• Lists of varying lengths → Should correctly merge all nodes.

---

Problem 11: Merge Two Sorted Lists

Explanation:

Given two sorted linked lists, merge them into one sorted list.

Approach:

1. Iterative Merge:
   • Use a dummy node to build the merged list.
   • Compare nodes and append the smaller one.
   • Attach remaining nodes when one list is exhausted.

Time & Space Complexity:

• Time Complexity: O(n + m), where n and m are list sizes.
• Space Complexity: O(1), since we modify lists in place.

Java Implementation:

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

public class MergeTwoSortedLists {
    /**
     * Merges two sorted linked lists.
     * @param l1 - first linked list
     * @param l2 - second linked list
     * @return merged sorted linked list
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
    
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);
        
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);
        
        ListNode result = mergeTwoLists(l1, l2);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

Example:

Input:

l1 = [1,2,4]
l2 = [1,3,4]

Output:

[1,1,2,3,4,4]

Edge Cases Considered:

• One empty list → Should return the non-empty list.
• Both lists empty → Should return null.
• Lists of different lengths → Should merge correctly.

Problem 12: Convert Sorted List to Binary Search Tree

Explanation:

Given a singly linked list where elements are sorted in ascending order, convert it to a height-balanced binary search tree (BST).

Approach:

1. In-order Simulation (Optimized Approach):
   • Find the middle element using a slow and fast pointer.
   • Recursively construct left and right subtrees.
   • Use in-order traversal to maintain sorting.

Time & Space Complexity:

• Time Complexity: O(n), since each node is processed once.
• Space Complexity: O(log n), due to recursive stack space.

Java Implementation:

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

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class ConvertSortedListToBST {
    /**
     * Converts a sorted linked list to a height-balanced BST.
     * @param head - head of the linked list
     * @return root of the BST
     */
    public static TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        return buildBST(head, null);
    }
    
    private static TreeNode buildBST(ListNode head, ListNode tail) {
        if (head == tail) return null;
        ListNode slow = head, fast = head;
        while (fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.left = buildBST(head, slow);
        root.right = buildBST(slow.next, tail);
        return root;
    }
    
    public static void main(String[] args) {
        ListNode head = new ListNode(-10);
        head.next = new ListNode(-3);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(5);
        head.next.next.next.next = new ListNode(9);
        
        TreeNode root = sortedListToBST(head);
        System.out.println("BST Root: " + root.val);
    }
}

Example:

Input:

head = [-10, -3, 0, 5, 9]

Output:

BST Root: 0

Edge Cases Considered:

• Empty list → Should return null.
• Single node → Should return a single-node tree.
• Large list → Should remain balanced.

---

Problem 13: Partition List

Explanation:

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x, while maintaining their relative order.

Approach:

1. Two-pointer approach:
   • Use two dummy nodes for less and greater lists.
   • Traverse the list and append nodes to corresponding lists.
   • Merge the two lists at the end.

Time & Space Complexity:

• Time Complexity: O(n), since we traverse the list once.
• Space Complexity: O(1), as we modify the list in place.

Java Implementation:

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

public class PartitionList {
    /**
     * Partitions a linked list around a given value x.
     * @param head - head of the linked list
     * @param x - partition value
     * @return head of the partitioned list
     */
    public static ListNode partition(ListNode head, int x) {
        ListNode lessDummy = new ListNode(0), greaterDummy = new ListNode(0);
        ListNode less = lessDummy, greater = greaterDummy;
        
        while (head != null) {
            if (head.val < x) {
                less.next = head;
                less = less.next;
            } else {
                greater.next = head;
                greater = greater.next;
            }
            head = head.next;
        }
        greater.next = null;
        less.next = greaterDummy.next;
        return lessDummy.next;
    }
    
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(4);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(2);
        
        ListNode result = partition(head, 3);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

Example:

Input:

head = [1,4,3,2,5,2], x = 3

Output:

[1,2,2,4,3,5]

Edge Cases Considered:

• All nodes less than x → List remains unchanged.
• All nodes greater than or equal to x → List remains unchanged.
• x is not in the list → Partitioning still applies.

---

Problem 14: Swap Nodes in Pairs

Explanation:

Given a linked list, swap every two adjacent nodes and return its head.

Approach:

1. Iterative Swapping:
   • Use a dummy node to simplify swaps.
   • Swap pairs of nodes by adjusting pointers.

Time & Space Complexity:

• Time Complexity: O(n), since we traverse the list once.
• Space Complexity: O(1), since we modify in place.

Java Implementation:

public class SwapNodesInPairs {
    /**
     * Swaps adjacent nodes in pairs.
     * @param head - head of the linked list
     * @return modified head of the list
     */
    public static ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        
        while (head != null && head.next != null) {
            ListNode first = head;
            ListNode second = head.next;
            
            prev.next = second;
            first.next = second.next;
            second.next = first;
            
            prev = first;
            head = first.next;
        }
        return dummy.next;
    }
    
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        
        ListNode result = swapPairs(head);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

Example:

Input:

head = [1,2,3,4]

Output:

[2,1,4,3]

Edge Cases Considered:

• Single node list → Should remain unchanged.
• Even-length list → All pairs swapped.
• Odd-length list → Last node remains unchanged.

---

Problem 15: Delete Node in a Linked List

Explanation:

Given a node in a singly linked list (not the head), delete it.

Approach:

1. Copy next node’s value and delete next node:
   • Copy the value of the next node into the current node.
   • Set current node’s next to next.next.

Time & Space Complexity:

• Time Complexity: O(1), since we perform only a few operations.
• Space Complexity: O(1), as we modify in place.

Java Implementation:

public class DeleteNodeInLinkedList {
    /**
     * Deletes a node in a linked list, given only access to that node.
     * @param node - node to be deleted
     */
    public static void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
    
    public static void main(String[] args) {
        ListNode head = new ListNode(4);
        head.next = new ListNode(5);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(9);
        
        deleteNode(head.next); // Delete node with value 5
        
        ListNode result = head;
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
    }
}

Example:

Input:

head = [4,5,1,9], node = 5

Output:

[4,1,9]

Edge Cases Considered:

• Last node deletion is not possible → Must avoid calling on the last node.
• Only one node in the list → Problem constraints do not allow this case.

---