706396. Reverse a sublist of a linked list
Reverse a Sublist of a Linked List
Slug: reverse-a-sublist-of-a-linked-list
Difficulty: Hard
Topic Tags: Linked List, Data Structures
Company Tags: Microsoft
Summary
Given a singly linked list and an integer k, reverse the kth sublist from the beginning of the linked list. For example, if the input list is 1 -> 2 -> 3 -> 4 -> 5 and k = 2, the output should be 1 -> 2 -> 5 -> 4 -> 3.
Detailed Explanation
To solve this problem, we can approach it in two steps: first, find the start of the sublist to be reversed, then reverse the sublist. To find the start of the sublist, we need to traverse k nodes from the beginning of the linked list. Once we reach the start of the sublist, we can reverse the sublist using a standard linked list reversal algorithm.
Here's a step-by-step breakdown of the solution:
- Initialize three pointers:
prev,curr, andnext. SetprevtoNULL,currto the beginning of the linked list, andnexttoNULL. - Traverse k nodes from the beginning of the linked list. Update
currandnextaccordingly. - Once we reach the start of the sublist, update
prevto point to the node before the current node (curr). Setnexttocurr -> next, effectively moving one step forward in the original list. - Reverse the sublist by updating
prev -> nextand settingcurrtonext. - Continue reversing the sublist until we reach the end of the sublist (i.e., when
currpoints to a node that is k nodes ahead of the start of the sublist). - Update the original linked list by moving the reversed sublist to its original position.
Time complexity: O(n), where n is the length of the linked list. Space complexity: O(1), as we only use a constant amount of space to store the pointers.
Optimized Solutions
Java
public Node reverseSublist(Node head, int k) {
if (head == null || k <= 0) {
return head;
}
Node prev = null;
Node curr = head;
for (int i = 0; i < k - 1; i++) {
prev = curr;
curr = curr.next;
}
Node start = curr;
Node end = start;
while (end.next != null) {
end = end.next;
}
end = end.next;
Node next = start.next;
while (next != end) {
Node temp = next.next;
next.next = start;
start = next;
next = temp;
}
if (prev != null) {
prev.next = end;
} else {
head = end;
}
return head;
}