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