Partitioning and Merging
16. Partition List
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/
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
}
}Algorithm Description: The problem asks to partition a linked list such that all nodes with values less than a given value
xcome before nodes with values greater than or equal tox. 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
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/
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;
}
}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
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/
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
}
}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
sortListfunction. 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
splitfunction. We initializeslowandfastpointers to the head of the list. Theslowpointer moves one step at a time, while thefastpointer moves two steps at a time. By the time thefastpointer reaches the end of the list, theslowpointer 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
sortListfunction 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
mergefunction. We create a dummy node and acurrpointer to build the merged list. We compare the values of the current nodes in the left and right lists, and append the smaller value tocurr.next. We update thecurrpointer 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 thecurr.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
The problem "Insertion Sort List" on LeetCode (https://leetcode.com/problems/insertion-sort-list/) asks us to sort a linked list using insertion sort.
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)
}
}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
dummywhich serves as the beginning of the sorted list. We also initialize a pointercurrto traverse the original list.We traverse the original list using the pointer
currand 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 pointerprevwhich 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 ofprevto the current node.After inserting the current node into the sorted list, we move to the next node in the original list by updating
currto 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
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/
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;
}
}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,
prevandcurr, to keep track of the current group.Iterate through the given linked list and increment a counter (
count) for each node.If
countis a multiple ofk, it means we have reached a group of sizek. In this case, call thereversefunction to reverse the nodes fromprev.nexttocurr.next, and updateprevandcurraccordingly.After iterating through the entire linked list, return the dummy node's next pointer (which will be the head of the reversed linked list).
Last updated