Partitioning and Merging

16. Partition List

1. Problem Description: Partition List Given the head of 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. You should preserve the original relative order of the nodes in each of the two partitions.

Problem Link: https://leetcode.com/problems/partition-list/

1. Optimized Java code for "Partition List" problem:

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

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode smallerHead = new ListNode(0); // head of the partition with smaller values
        ListNode smallerTail = smallerHead; // tail of the partition with smaller values
        
        ListNode greaterHead = new ListNode(0); // head of the partition with greater or equal values
        ListNode greaterTail = greaterHead; // tail of the partition with greater or equal values
        
        while (head != null) {
            if (head.val < x) {
                smallerTail.next = head;
                smallerTail = smallerTail.next;
            } else {
                greaterTail.next = head;
                greaterTail = greaterTail.next;
            }
            head = head.next;
        }
        
        smallerTail.next = greaterHead.next; // merge smaller and greater partitions
        greaterTail.next = null; // set next of greaterTail to null to remove any circular references
        
        return smallerHead.next; // return the merged partition
    }
}

1. Algorithm Description: The problem asks to partition a linked list such that all nodes with values less than a given value x come before nodes with values greater than or equal to x. The relative order of the nodes should be preserved.

To solve this problem efficiently, we initialize two separate partitions, smallerHead and greaterHead, which are initially empty. We also maintain smallerTail and greaterTail as the respective tails of the two partitions.

We iterate through the given linked list and for each node, compare its value with x. If the value is less than x, we append it to the smallerTail and update smallerTail as the new appended node. If the value is greater than or equal to x, we append it to the greaterTail and update greaterTail as the new appended node.

After iterating through the entire list, we merge the two partitions by setting smallerTail.next to greaterHead.next. This connects the two partitions, keeping the relative order intact. Finally, we set greaterTail.next to null to remove any circular references.

The result is the linked list formed by smallerHead.next, which is the head of the partition with smaller values after partitioning.

During an interview, it is important to clearly identify the problem requirements and constraints. Break the problem into smaller steps and think of appropriate data structures and algorithms to solve each step. One approach could be to initialize two partitions and iteratively build them while traversing the list. Discuss the time and space complexity of the solution. Writing clean and well-commented code will also demonstrate your problem-solving and coding skills.

17. Merge k Sorted Lists

1. Problem Description and Link:

The problem is to merge k sorted linked lists and return it as one sorted list. The input is an array of linked lists, and our task is to merge them into a single sorted linked list and return the head of that list.

LeetCode Link: https://leetcode.com/problems/merge-k-sorted-lists/

1. Optimized Java Code with Detailed Comments:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        
        // Create a priority queue (min-heap) with custom comparator
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
            public int compare(ListNode a, ListNode b) {
                return a.val - b.val;
            }
        });
        
        // Add the heads of all lists to the min-heap
        for (ListNode node : lists) {
            if (node != null) {
                queue.add(node);
            }
        }
        
        // Create a dummy node and a pointer to it
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        // While there are elements in the min-heap
        while (!queue.isEmpty()) {
            // Get the smallest element from the min-heap
            ListNode minNode = queue.poll();
            
            // Append the smallest element to the result list
            current.next = minNode;
            current = current.next;
            
            // Move to the next element of the current list
            if (minNode.next != null) {
                queue.add(minNode.next);
            }
        }
        
        // Return the sorted merged list
        return dummy.next;
    }
}

1. Detailed Description of Algorithm:

• To merge k sorted lists efficiently, we can make use of a min-heap (priority queue).

• We initialize a min-heap with a custom comparator that compares ListNode objects based on their values.

• We iterate through all the lists and add their heads (first element) to the min-heap.

• We initialize a dummy node and a pointer to it, which will be used to build the sorted merged list.

• We repeatedly remove the smallest element from the min-heap and add it to the sorted merged list.

• After removing an element, we check if it has a next element. If it does, we add the next element to the min-heap.

• We continue this process until the min-heap is empty.

• Finally, we return the head of the sorted merged list.

During an interview, the key points to emphasize are:

• Efficiently merging k sorted lists using a min-heap can be achieved by leveraging the heap's property of keeping the smallest element at the top.

• Understanding how to use a custom comparator to compare ListNode objects based on their values.

• Understanding the concept of a dummy node and a pointer to it, which helps in building the sorted merged list.

• Recognizing the use of a while-loop to repeatedly remove the smallest element from the min-heap and add it to the sorted merged list.

• Noting that the time complexity of this approach is O(N log k), where N is the total number of elements across all lists and k is the number of lists. This is because we perform log k operations (removal/addition) on a min-heap for each of the N elements.

• Mentioning that the space complexity is O(k) because we store a maximum of k elements in the min-heap.

18. Sort List

1. Problem Description: The problem "Sort List" on LeetCode is given a linked list, sort it in O(n log n) time complexity.

Link to the problem: https://leetcode.com/problems/sort-list/

1. Optimized Java Code with Detailed Comments:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        // Base case: If the list is empty or contains only one node, return it
        if (head == null || head.next == null) {
            return head;
        }
        
        // Split the list into two halves using the 'split' function
        ListNode mid = split(head);
        
        // Recursive calls to sort the two halves
        ListNode left = sortList(head);
        ListNode right = sortList(mid);
        
        // Merge the sorted halves using the 'merge' function
        return merge(left, right);
    }
    
    // Function to split the list into two halves
    private ListNode split(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = null;
        
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        
        prev.next = null; // Break the link between the two halves
        return slow; // Return the head of the second half
    }
    
    // Function to merge two sorted lists
    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        
        while (left != null && right != null) {
            if (left.val <= right.val) {
                curr.next = left;
                left = left.next;
            } else {
                curr.next = right;
                right = right.next;
            }
            curr = curr.next;
        }
        
        if (left != null) {
            curr.next = left;
        }
        
        if (right != null) {
            curr.next = right;
        }
        
        return dummy.next; // Return the merged list
    }
}

1. Detailed Description:

• In this problem, we can solve it efficiently using the Merge Sort algorithm. The idea is to recursively divide the linked list into halves until we reach a single-node or an empty list. Then, we merge the sorted halves back together using the merge function.

• The algorithm starts by implementing the sortList function. It acts as the entry point for the recursive merge sort. First, we handle the base case where we return the list if it is empty or contains only one node.

• To divide the list into two halves, we use the split function. We initialize slow and fast pointers to the head of the list. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. By the time the fast pointer reaches the end of the list, the slow pointer will be at the midpoint. We also keep a reference to the previous node (prev) so that we can break the link between the two halves.

• After splitting the list, we recursively call the sortList function on both halves. This step continues until we reach the base case of an empty or single-node list.

• Finally, we merge the sorted halves using the merge function. We create a dummy node and a curr pointer to build the merged list. We compare the values of the current nodes in the left and right lists, and append the smaller value to curr.next. We update the curr pointer and the corresponding pointer in the left/right lists accordingly. This process continues until one of the lists becomes empty. We then append the remaining nodes from the non-empty list to the curr.next.

• At the end, we return the next node of the dummy node, which is the head of the merged and sorted list.

• This algorithm has a time complexity of O(n log n) since we divide the list into halves recursively and merge them together in a balanced manner. The space complexity is O(log n) due to the recursive call stack.

• During interviews, it is important to communicate the steps and thought process clearly. Explain how merging two sorted lists works and how the merge sort algorithm is utilized for linked lists. Discuss the time and space complexity of the algorithm to showcase your understanding.

19. Insertion Sort List

1. The problem "Insertion Sort List" on LeetCode (https://leetcode.com/problems/insertion-sort-list/) asks us to sort a linked list using insertion sort.

2. Optimized Java code for "Insertion Sort List" with detailed comments:

class ListNode {
    int val;
    ListNode next;

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

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(0);  // Dummy node to serve as the beginning of sorted list
        ListNode curr = head;  // Pointer to traverse the original list

        while (curr != null) {
            ListNode nextNode = curr.next;  // Store the next node before insertion

            // Find the position to insert the current node in the sorted list
            ListNode prev = dummy;
            while (prev.next != null && prev.next.val < curr.val) {
                prev = prev.next;
            }

            // Insert the current node into the sorted list
            curr.next = prev.next;
            prev.next = curr;

            curr = nextNode;  // Move to the next node in the original list
        }

        return dummy.next;  // Return the sorted list (excluding the dummy node)
    }
}

1. Detailed description of the algorithm and how to think through it during an interview:

• The problem asks us to perform insertion sort on a singly linked list. The idea behind insertion sort is to insert each element into its correct position in a sorted sublist.

• We start by creating a dummy node called dummy which serves as the beginning of the sorted list. We also initialize a pointer curr to traverse the original list.

• We traverse the original list using the pointer curr and for each node, we find its correct position in the sorted list by comparing its value with the values of nodes in the sorted list. To find the correct position, we maintain another pointer prev which starts at the dummy node and moves forward until it reaches the end of the sorted list or finds a value greater than or equal to the current node's value.

• Once we find the correct position for the current node, we insert it by rearranging the pointers. We set the next pointer of the current node to the next node of prev, and then set the next pointer of prev to the current node.

• After inserting the current node into the sorted list, we move to the next node in the original list by updating curr to its next node.

• We repeat this process until we traverse the entire original list. At the end, the dummy node's next pointer will point to the head of the sorted list.

• Lastly, we return the head of the sorted list (excluding the dummy node).

During an interview, it is important to communicate your thought process clearly and step-by-step. You can begin by explaining the problem and understanding the concept of insertion sort. Then, you can break down the problem into smaller steps and discuss the data structures and variables needed to solve it. Finally, you can explain the algorithm and how each step contributes to the final solution.

20. Reverse Nodes in k-Group

1. The problem is called "Reverse Nodes in k-Group" on LeetCode. Here is the link to the problem: https://leetcode.com/problems/reverse-nodes-in-k-group/

2. Here is the optimized Java code for the "Reverse Nodes in k-Group" problem:

/*
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode prev = dummy;
        ListNode curr = head;
        
        int count = 0;
        while (curr != null) {
            count++;
            if (count % k == 0) {
                prev = reverse(prev, curr.next);
                curr = prev.next;
            } else {
                curr = curr.next;
            }
        }
        
        return dummy.next;
    }
    
    private ListNode reverse(ListNode prev, ListNode next) {
        ListNode last = prev.next;
        ListNode curr = last.next;
        
        while (curr != next) {
            last.next = curr.next;
            curr.next = prev.next;
            prev.next = curr;
            curr = last.next;
        }
        
        return last;
    }
}

1. The "Reverse Nodes in k-Group" problem involves reversing nodes in a linked list in groups of size k. The algorithm can be broken down into the following steps:

• Create a dummy node and set its next pointer to the head of the given linked list.

• Initialize two pointers, prev and curr, to keep track of the current group.

• Iterate through the given linked list and increment a counter (count) for each node.

• If count is a multiple of k, it means we have reached a group of size k. In this case, call the reverse function to reverse the nodes from prev.next to curr.next, and update prev and curr accordingly.

• After iterating through the entire linked list, return the dummy node's next pointer (which will be the head of the reversed linked list).