Ketan Mehta
BAN USERI am highly skilled resource who can easily adapt to a challenging environment, progressively learn and add value to the organization as I grow.
Recursive method without changing the list. It can even be done in iterative way.
public void printReverseLL(LinkedListNode<String> currentNode){
// check if the list is empty
if(currentNode == null){
return;
}
// If not the end of list, then call the same function with next node
printReverseLL(currentNode.getNext());
// Print the value before returning
System.out.print(currentNode.getValue());
}
Ask follow up questions to interviewer like can I use another data structure like Queues. If they just wanted to avoid using arrays, then it can be possible by below solutions. Need to be sure before you approach further, since nothing mentioned of doing in O(1) space
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class RearrangeNumbers {
public static void main(String[] args) {
int[] num = { 2, -1, -3, -7, -8, 9, 5, -5, -7 };
System.out.println("Initial num is: \n"
+ Arrays.toString(num));
System.out.println("\nAfter Rarranging num is: \n"
+ Arrays.toString(rearrangeNum(num)));
}
public static int[] rearrangeNum(int[] num){
/* Check corner conditions.
* can't rearrange anything with size 1 */
if(num == null || num.length < 2){
return num;
}
// Use Queues, so that we have first in first out (FIFO)
Queue<Integer> posNumQ = new LinkedList<Integer>();
Queue<Integer> negNumQ = new LinkedList<Integer>();
/* Scan through all the num in array and
* store in respective queues. Runs in O(n) time*/
for(int i=0; i<num.length; i++){
if(num[i] >= 0)
posNumQ.add(num[i]);
else
negNumQ.add(num[i]);
}
int index = 0; // use this index to rearrange the values
/* Scan through all the num in array and
* rearrange in respective position. Runs in O(n) time*/
for(int i=0; i<num.length; i++){
if(index % 2 == 0 && !posNumQ.isEmpty()){
num[index] = posNumQ.poll();
index++;
}else if(index % 2 != 0 && !negNumQ.isEmpty()){
num[index] = negNumQ.poll();
index++;
}
}
/* If there is no positive number(or negative) left,
* then all the remaining negative numbers(or positive)
* are appended to the end of the array. */
while(!negNumQ.isEmpty()){
num[index] = negNumQ.poll();
index++;
}
while(!posNumQ.isEmpty()){
num[index] = posNumQ.poll();
index++;
}
return num;
}
}
Creating your own Linked List class with private head field, this is possible to do so recursively.
public void recursiveReverse(LinkedListNode<T> currentNode){
// check if the list is empty
if(currentNode == null){
return;
}
/* if we have recursed till the last node in the list
then we have to set it to head. This is recursive base case. */
if(currentNode.getNext() == null){
// set list head to current last node (tail) since we are reversing list
this.head = currentNode;
return; //since this is the base case
}
// If not the end of list, then call the same function with next node
recursiveReverse(currentNode.getNext());
// add link from next to previous, will create cycle temporary
// Ex: 1-->2 will become 1<-->2
currentNode.getNext().setNext(currentNode);
// Set the old next pointer to null, since reversing list
// So now it will become 2-->1 from above example
currentNode.setNext(null);
}
Test Cases:
1) Both Linked List have same length.
2) First Linked List length < Second Linked List length
3) First Linked List length > Second Linked List length
4) Both Linked List are null
5) First Linked List is null
6) Second Linked List is null
Below is recursive solution to the problem. It can be solved iteratively as well, but recursive solution seems more cleaner.
public LinkedListNode<Integer> alternateAdd(LinkedListNode<Integer> list1,
LinkedListNode<Integer> list2){
if(list1 == null){
return list2;
}else if(list2 == null){
return list1;
}else{
list2.setNext(alternateAdd(list1.getNext(), list2.getNext()));
list1.setNext(list2);
return list1;
}
}
/** Convert 1-->2-->3-->4-->5-->1-->2-->null into
* 1-->1-->2-->2-->3-->4-->5-->null */
public LinkedListNode<Integer> arrangeList(LinkedListNode<Integer> head){
// Base conditions i.e. either list is empty or contains just one node
if(head == null || head.getNext() == null){
return head;
}
LinkedListNode<Integer> first_list = head;
LinkedListNode<Integer> splitNode = head;
LinkedListNode<Integer> sec_list = head.getNext();
// Traverse to position/point each node in proper location
while(splitNode != null && sec_list != null
&& splitNode.getValue() < sec_list.getValue()){
splitNode = splitNode.getNext();
sec_list = sec_list.getNext();
}
/* Another corner condition: Traversed complete list
* but didn't found any new secondary list
* i.e existing list is already arranged */
if(sec_list == null){
return head;
}
/* if my sec_list contains smaller number then rearrange it
* so that my first_list is always of smaller value */
while(sec_list != null
&& first_list.getValue() > sec_list.getValue()){
splitNode.setNext(sec_list.getNext());
sec_list.setNext(first_list);
head = sec_list;
sec_list = splitNode.getNext();
}
/* traverse till end of second_list is empty or
first_list intersects with second list */
while(sec_list != null && first_list != sec_list){
if(first_list.getNext().getValue() >= sec_list.getValue()){
splitNode.setNext(sec_list.getNext());
sec_list.setNext(first_list.getNext());
first_list.setNext(sec_list);
sec_list = splitNode.getNext();
}else if(first_list.getNext().getValue() < sec_list.getValue()){
first_list = first_list.getNext();
}else{
sec_list = sec_list.getNext();
}
}
// return the head, since head may change based on the initial link list
return head;
}
Reverse the list and display it. Below is code to reverse the linked list using linked list node. No other data structure used. Once you get the linked list, you can print it out.
- Ketan Mehta October 03, 2014