Reverse Nodes in k-Group
The task is to reverse the nodes in groups of kk in a given linked list, where kk is a positive integer, and at most the length of the linked list. If any remaining nodes are not part of a group of kk, they should remain in their original order.
It is not allowed to change the values of the nodes in the linked list. Only the order of the nodes can be modified.
Note: Use only O(1)O(1) extra memory space.
{
public static ListNode reverseKGroups(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode ptr = dummy;
while (ptr != null) {
ListNode tracker = ptr;
for (int i = 0; i < k; i++) {
if (tracker == null) {
break;
}
tracker = tracker.next;
}
if (tracker == null) {
break;
}
ListNode[] updatedNodes = LinkedListReversal.reverseLinkedList(ptr.next, k);
ListNode previous = updatedNodes[0];
ListNode current = updatedNodes[1];
ListNode lastNodeOfReversedGroup = ptr.next;
lastNodeOfReversedGroup.next = current;
ptr.next = previous;
ptr = lastNodeOfReversedGroup;
}
return dummy.next;
}
static ListNode[] reverseLinkedList(ListNode node, int k){
ListNode previous = null;
ListNode current = node;
ListNode next = null;
for (int i = 0; i < k; i++) {
next = current.next;
current.next = previous;
previous = current;
current = next;
}
return new ListNode[]{previous, current};
}Reverse Linked List II
Given a singly linked list with nn nodes and two positions, left and right, the objective is to reverse the nodes of the list from left to right. Return the modified list.
- We initialize a dummy node, which will be helpful in scenarios where the reversal of the sublist starts from the head of the list.
- We set the next node of dummy to point to the head of the list.
- We initialize a pointer, prev, to the dummy node. This pointer will help us reconnect the sublist to the entire list after it has been reversed.
- We use a loop to traverse the list with the prev pointer and until it reaches the node immediately before the sublist to be reversed.
- We initialize a curr pointer, which points to the node next to prev.
- Another loop is used to reverse the sublist. This loop iterates right - left times, which is the number of nodes in the sublist minus one:
- We set next_node to curr.next, representing the node to be moved to the front of the reversed sublist.
- We update curr.next to next_node.next, effectively removing next_node from its current position in the sublist.
- We set next_node.next to prev.next, inserting next_node at the beginning of the reversed sublist.
- We update prev.next to next_node, adjusting the pointer to next_node for the next iteration.
- Finally, we return dummy.next, which is the head of the modified linked list.
- cur and prev nodes never change
// Function to reverse the sublist within the linked list
public static ListNode reverseBetween(ListNode head, int left, int right) {
// If the list is empty or left position is the same as right, return the original list
if (head == null || left == right) {
return head;
}
// Create a dummy node to handle edge case when left = 1
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
// Move prev to the node just before the left position
for (int i = 0; i < left - 1; i++) {
prev = prev.next;
}
// Current node is the node at left position
ListNode curr = prev.next;
// Reverse the portion of the linked list between left and right positions
for (int i = 0; i < right - left; i++) {
ListNode nextNode = curr.next;
curr.next = nextNode.next;
nextNode.next = prev.next;
prev.next = nextNode;
}
// Return the updated head of the linked list
return dummy.next;
}
Reorder List
Given the head of a singly linked list, reorder the list as if it were folded on itself. For example, if the list is represented as follows:
L0L0 → L1L1 → L2L2 → … → Ln−2Ln−2 → Ln−1Ln−1 → LnLn
This is how you’ll reorder it:
L0L0 → LnLn → L1L1 → Ln−1Ln−1 → L2L2 → Ln−2Ln−2 → …
You don’t need to modify the values in the list’s nodes; only the links between nodes need to be changed.
Constraints:
public static ListNode reorderList(ListNode head) {
if (head == null || head.next == null) return head;
// 1) find middle (slow at end of first half)
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 2) split
ListNode second = slow.next;
slow.next = null;
// 3) reverse second half
ListNode prev = null, curr = second;
while (curr != null) {
ListNode nxt = curr.next;
curr.next = prev;
prev = curr;
curr = nxt;
}
second = prev; // head of reversed second half
// 4) merge
ListNode first = head;
while (second != null) {
ListNode t1 = first.next;
ListNode t2 = second.next;
first.next = second;
second.next = t1;
first = t1;
second = t2;
}
return head;
}Swapping Nodes in a Linked List
Let’s solve the Swapping Nodes in a Linked List problem using the In-Place Manipulation of a Linked List pattern.
Statement
Given the head of a linked list and an integer, k, return the head of the linked list after swapping the values of the kthkth node from the beginning and the kthkth node from the end of the linked list.
Note: We’ll number the nodes of the linked list starting from 11 to nn.
Constraints:
The linked list will have n number of nodes. 1≤1≤ k ≤≤ n ≤500≤500 −5000≤−5000≤ Node.value ≤5000≤5000
public class Solution {
public static void swap(ListNode node1, ListNode node2) {
int temp = node1.val;
node1.val = node2.val;
node2.val = temp;
}
public static ListNode swapNodes(ListNode head, int k) {
if (head == null) {
return head;
}
int count = 0;
// front and end pointers will be used to track the kth node from
// the start and end of the linked list, respectively
ListNode front = null;
ListNode end = null;
ListNode curr = head;
while (curr != null) {
count += 1;
// if end is not null, it means the kth node from the beginning has
// been found, we can start moving the end pointer to find the
// kth node from the end of the linked list
if (end != null) {
end = end.next;
}
// if the count has become equal to k, it means the curr is
// pointing the kth node at the begining of the linked list
if (count == k) {
front = curr;
end = head;
}
curr = curr.next;
}
// swap the values of two nodes
swap(front, end);
return head;
}Reverse Nodes in Even Length Groups
Let’s solve the Reverse Nodes in Even Length Groups problem using the In-Place Manipulation of a Linked List pattern.
Statement
Given the head of a linked list, the nodes in it are assigned to each group in a sequential manner. The length of these groups follows the sequence of natural numbers. Natural numbers are positive whole numbers denoted by (1,2,3,4…)(1,2,3,4…).
In other words:
The 1st1st node is assigned to the first group. The 2nd2nd and 3rd3rd nodes are assigned to the second group. The 4th4th, 5th5th, and 6th6th nodes are assigned to the third group, and so on.
Your task is to reverse the nodes in each group with an even number of nodes and return the head of the modified linked list.
public static ListNode reverseEvenLengthGroups(ListNode head)
{
// Node immediately before the current group
ListNode prev = head;
ListNode node, reverse, currNext, curr, prevNext = null;
// The head doesn't need to be reversed since it's a group of one node,
// so starts with length 2
int groupLen = 2;
int numNodes = 0;
while(prev.next!= null)
{
node = prev;
numNodes = 0;
// traversing all the nodes of the current group
for (int i = 0; i < groupLen; i ++)
{
if(node.next == null)
break;
numNodes += 1;
node=node.next;
}
// odd length
if(numNodes % 2 != 0) {
prev = node;
}
// even length
else {
reverse = node.next;
curr = prev.next;
for(int j=0; j < numNodes;j++){
currNext = curr.next;
curr.next = reverse;
reverse = curr;
curr = currNext;
}
// updating the prev pointer after reversal of the even group
prevNext = prev.next;
prev.next = node;
prev = prevNext;
}
// increment 1 by one and move to the next group
groupLen += 1;
}
return head;
}Remove Duplicates from Sorted List
Let’s solve the Remove Duplicates from Sorted List problem using the In-Place Manipulation of a Linked List pattern.
Statement
Given the head of a sorted linked list, remove all duplicates such that each element appears only once, and return the list in sorted order.
Constraints:
0≤0≤ n ≤300≤300, where n is the number of nodes in the list. −100≤−100≤ Node.val ≤100≤100 The list is guaranteed to be sorted in ascending order.
public static ListNode removeDuplicates(ListNode head) {
ListNode current = head;
while (current != null && current.next != null) {
if (current.next.val==current.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}Remove Linked List Elements
Let’s solve the Remove Linked List Elements problem using the In-place Manipulation of a Linked List pattern.
Statement
You are given the head of a linked list and an integer k. Remove all nodes from the linked list where the node’s value equals k, and return the head of the updated list.
Constraints:
The number of nodes in the list is in the range [0,103][0,103]. 1≤1≤ Node.val ≤50≤50 0≤0≤ k ≤50≤50
public static ListNode removeElements(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy, curr = head;
while (curr != null) {
if (curr.val == k) {
prev.next = curr.next;
curr = curr.next;
} else {
prev = curr;
curr = curr.next;
}
}
return dummy.next;
}Split Linked List in Parts
Let’s solve the Split Linked List in Parts problem using the In-place Manipulation of a Linked List pattern.
Statement
You are given head of a singly linked list and an integer, k. Your task is to split the linked list into k consecutive parts.
Each part should have a size as equal as possible, with the difference between any two parts being at most 11. If the list cannot be evenly divided, the earlier parts should have more nodes than the later ones. Any parts that cannot be filled with nodes should be represented as NULL. The parts must appear in the same order as in the input-linked list.
Return an array of the k parts, maintaining the specified conditions.
// Function to split the linked list into k parts
public static ListNode[] splitListToParts(ListNode head, int k) {
ListNode[] ans = new ListNode[k];
// Calculate the total size of the linked list
int size = 0;
ListNode current = head;
while (current != null) {
size++;
current = current.next;
}
// Calculate the base size of each part
int split = size / k;
// Calculate the number of extra nodes to be distributed among the first few parts
int remaining = size % k;
current = head;
ListNode prev = null;
for (int i = 0; i < k; i++) {
// Start a new part
ans[i] = current;
// Determine the size of the current part
int currentSize = split + (remaining > 0 ? 1 : 0);
if (remaining > 0) remaining--;
// Traverse the current part to its end
for (int j = 0; j < currentSize; j++) {
prev = current;
if (current != null) {
current = current.next;
}
}
// Disconnect the current part from the rest of the list
if (prev != null) {
prev.next = null;
}
}
return ans;
}Insert into a Sorted Circular Linked List
Let’s solve the Insert into a Sorted Circular Linked List problem using the In-Place Manipulation of a Linked List pattern.
Statement
You’re given a reference to a node, head, in a circular linked list, where the values are sorted in non-decreasing order. The list is circular, so the last node points to the first node. However, the head can be any node in the list—it is not guaranteed to be the node with the smallest value.
Your task is to insert a new value, insertVal, into the list so that it remains sorted and circular after the insertion.
You can choose any of the multiple valid spots where the value can be inserted while maintaining the sort order. If the list is empty (i.e., the given node is NULL), create a new circular list with a single node containing insertVal, and return that node. Otherwise, return the head node after insertion.
// Function to insert a value into the circular linked list
public Node insert(Node head, int insertVal)
{
// Case: Empty list — create a new node that points to itself
if (head == null) {
Node newNode = new Node(insertVal);
newNode.next = newNode; // Make it circular
return newNode;
}
Node prev = head;
Node curr = head.next;
boolean flag = false; // To check whether we found the correct position
while (true) {
// Case 1: Insert between two sorted nodes (normal case)
if (prev.val <= insertVal && insertVal <= curr.val) {
flag = true;
}
// Case 2: At the rotation point (max -> min)
else if (prev.val > curr.val) {
// InsertVal is either greater than max or smaller than min
if (insertVal >= prev.val || insertVal <= curr.val) {
flag = true;
}
}
if (flag) {
prev.next = new Node(insertVal, curr);
return head;
}
prev = curr;
curr = curr.next;
if (prev == head) {
break;
}
}
// Case 3: No valid spot found, insert at any position
prev.next = new Node(insertVal, curr);
return head;
}Odd Even Linked List
Let’s solve the Odd Even Linked List problem using the In-Place Manipulation of a Linked List pattern.
Statement
Given the head of a singly linked list, rearrange the nodes so that all nodes at odd indexes appear first, followed by all nodes at even indexes.
The first node in the list is considered at odd index 1, the second at even index 2, and so on. Within the odd group and the even group, the relative order of the nodes must remain the same as in the original list.
Return the head of the reordered linked list.
// Function to rearrange the linked list
public ListNode oddEvenList(ListNode head) {
if (head == null) return null; // Edge case: if the list is empty, just return null
ListNode odd = head; // Pointer to the first node (odd index)
ListNode even = head.next; // Pointer to the second node (even index)
ListNode evenHead = even; // Keep the head of the even list to connect later
// Traverse the list until there are no more even nodes
while (even != null && even.next != null) {
odd.next = even.next; // Link current odd node to the next odd node
odd = odd.next; // Move odd pointer one step forward
even.next = odd.next; // Link current even node to the next even node
even = even.next; // Move even pointer one step forward
}
odd.next = evenHead; // Finally, connect the last odd node to the head of the even list
return head; // Return the rearranged list head
}
