K reverse a linked list with increasing K ~ KodeKnight
Example
Eg. 1 - 2 - 3 - 4 - 5 - 6 - 7
output - 1 - 3 - 2 - 6 - 5- 4 - 7
Read full article from K reverse a linked list with increasing K ~ KodeKnight
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
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;
}