Problem
Example
Eg. 1 - 2 - 3 - 4 - 5 - 6 - 7
output - 1 - 3 - 2 - 6 - 5- 4 - 7
Time complexity - O(n)
Reverse k elements in the linked list such that k goes on increasing
Example
Eg. 1 - 2 - 3 - 4 - 5 - 6 - 7
output - 1 - 3 - 2 - 6 - 5- 4 - 7
Solution
You can take this problem here. Here we are just increasing k. public static ListNode<Integer> reverseSubLinkLists(ListNode<Integer> headerNode) {
ListNode<Integer> nextNode = headerNode.next;
ListNode<Integer> startNode = null;
ListNode<Integer> endNode = null;
int k = 2;
while (nextNode != null) {
startNode = nextNode;
endNode = nextNode;
for (int i = 1; i < k; i++) {
endNode = endNode.next;
if (endNode == null) {
break;
}
}
if (endNode != null) {
// Save the node next to endNode
nextNode = endNode.next;
// Unlink the endNode
endNode.next = null;
// Reverse the list starting from startNode
startNode = reverseListIterative(startNode);
k++;
} else {
nextNode = null;
// // Save the node next to endNode
// nextNode = endNode.next;
// // Unlink the endNode
// endNode.next = null;
// Reverse the list starting from startNode
startNode = reverseListIterative(startNode);
}
if (headerNode == null) {
headerNode = startNode;
} else {
headerNode.next = startNode;
ListNode<Integer> temp = startNode;
while(temp!=null){
if(temp.next==null){
break;
}
temp = temp.next;
}
headerNode = temp;
}
}
return headerNode;
}
public static ListNode<Integer> reverseListIterative(ListNode<Integer> headerNode) {
ListNode<Integer> prevNode = null;
ListNode<Integer> currNode = headerNode;
ListNode<Integer> nextNode = null;
while (currNode != null) {
nextNode = currNode.next;
currNode.next = prevNode;
prevNode = currNode;
currNode = nextNode;
}
return prevNode;
}
Time complexity - O(n)







0 comments:
Post a Comment