May 25, 2014

Reverse a linked list in pairs (alternate pairs of nodes) - Recursive and Iterative

Problem Statement :- Reverse a linked list in such a way that, pair of elements are reversed and linked list internal structure is maintained. Solve using recursive and non-recursive approach.
Sample Input and Output:- 
Inputs:  12 --> 18 -->  172 --> 62 --> 632 --> 192 --> 34
Output:  18 --> 12 -->  62  --> 172 --> 192 --> 632 --> 34
Inputs:  12 --> 18 -->  172 --> 62 --> 632 --> 192 
Output:  18 --> 12 -->  62  --> 172 --> 192 --> 632

Recursive implementation - reverse a linked list in pairs 

Algorithm:-
1) Reverse pair of nodes of  input list and store references of next pair of nodes using next2nextNode. keep track of previous node using previous reference.
2) Recursively call for rest of the list and link the two sub-lists(head.next = reverseLinkedListInPairsRecursive(next2nextNode) )
3) Since, previous is storing first node of each pair, so return previous as new head of the list.
4) Check for special cases for empty list and one node list.
/* Recursive- Reverses the linked list in pairs and returns new head node. */
private Node reverseLinkedListInPairsRecursive(Node head) {
 Node current = head;
 Node nextNode = null;
 Node next2nextNode = null;
 Node previous = null;
 /* Check for empty and one node list */
 if (current == null || current.next == null)
  return current;

 /* Reverse pair of nodes - check current and current.next is not null */
 if (current != null && current.next != null) {
  nextNode = current.next;
  next2nextNode = nextNode.next;
  current.next = previous;
  nextNode.next = current;
  previous = nextNode;
 }
 /*
  * Recursive call for next pairs and make rest of the list as next of
  * first node
  */
 if (nextNode != null) {
  head.next = reverseLinkedListInPairsRecursive(next2nextNode);
 }

 /* Return previous as new head of the input list */
 return previous;
}

Iterative approach / Non-recursive implementation - reverse a linked list in pairs

Algorithm:-
1. Check for he null list or one node list, if true return that node.
2. Loop the list, until current node and next node is not null, revert pair of node references(if Node1 - > Node2 it becomes Node2 -> Node1)
3. Update previous reference and head(only first iteration).
4. Finally, check for isolated node, and return modified head.
/* Iterative- Reverses the linked list in pairs and returns new head node. */
private Node reverseLinkedListInPairsIterative(Node head) {
 Node current = head;
 Node nextNode = null;
 Node next2nextNode = null;
 Node previous = null;

 /* Check for empty and one node list */
 if (current == null || current.next == null)
  return current;

 /* Loop rest of the list and reverse pairs of nodes */
 while (current != null && current.next != null) {
  /* Swap references of two nodes */
  nextNode = current.next;
  next2nextNode = nextNode.next;
  nextNode.next = current;
  current.next = next2nextNode;

  /*
   * Update previous.next and head :- head is updated for first time
   * and after that update previous.next to connect next pairs
   */
  if (previous == null) {
   head = nextNode;
  } else {
   previous.next = nextNode;
  }

  previous = current;
  current = next2nextNode;
 }
 /* Check for isolated node in pairs - when one node is left */
 if (current != null) {
  previous.next = current;
 }
 /* Return modified head of the list */
 return head;
}

Complete sample program - recursive and iterative implementation 

package com.devinline.linkedlist;

public class ReverseLinkedListElementsInPairs {
 /* Recursive- Reverses the linked list in pairs and returns new head node. */
 private Node reverseLinkedListInPairsRecursive(Node head) {
  Node current = head;
  Node nextNode = null;
  Node next2nextNode = null;
  Node previous = null;
  /* Check for empty and one node list */
  if (current == null || current.next == null)
   return current;

  /* Reverse pair of nodes - check current and current.next is not null */
  if (current != null && current.next != null) {
   nextNode = current.next;
   next2nextNode = nextNode.next;
   current.next = previous;
   nextNode.next = current;
   previous = nextNode;
  }
  /*
   * Recursive call for next pairs and make rest of the list as next of
   * first node
   */
  if (nextNode != null) {
   head.next = reverseLinkedListInPairsRecursive(next2nextNode);
  }

  /* Return previous as new head of the input list */
  return previous;
 }

 /* Iterative- Reverses the linked list in pairs and returns new head node. */
 private Node reverseLinkedListInPairsIterative(Node head) {
  Node current = head;
  Node nextNode = null;
  Node next2nextNode = null;
  Node previous = null;

  /* Check for empty and one node list */
  if (current == null || current.next == null)
   return current;

  /* Loop rest of the list and reverse pairs of nodes */
  while (current != null && current.next != null) {
   /* Swap references of two nodes */
   nextNode = current.next;
   next2nextNode = nextNode.next;
   nextNode.next = current;
   current.next = next2nextNode;

   /*
    * Update previous.next and head :- head is updated for first time
    * and after that update previous.next to connect next pairs
    */
   if (previous == null) {
    head = nextNode;
   } else {
    previous.next = nextNode;
   }

   previous = current;
   current = next2nextNode;
  }
  /* Check for isolated node in pairs - when one node is left */
  if (current != null) {
   previous.next = current;
  }
  /* Return modified head of the list */
  return head;
 }

 /* Display data of nodes/iterate linked list */
 private static void displayLinkedList(Node head) {
  Node current = head;
  if (head != null) {
   System.out.print("[ ");
   while (current != null) {
    System.out.print(current.data + " ");
    current = current.next;
   }
   System.out.print(" ]");
  } else {
   System.out.println("Linked list is empty.");
  }

 }

 class Node {
  public int data;
  public Node next; // reference(handler) for next Node.

  public Node(int data) {
   this.data = data;
   this.next = null;
  }
 }

 public static void main(String[] args) {
  ReverseLinkedListElementsInPairs rpll = new ReverseLinkedListElementsInPairs();
  Node modifiedHead = null;
  System.out.println("------1st test-----");
  Node node1 = rpll.new Node(12);
  Node node2 = rpll.new Node(18);
  Node node3 = rpll.new Node(172);
  Node node4 = rpll.new Node(62);
  Node node5 = rpll.new Node(632);
  Node node6 = rpll.new Node(192);
  Node head = node1;
  node1.next = node2;
  node1.next.next = node3;
  node1.next.next.next = node4;
  node1.next.next.next.next = node5;
  node1.next.next.next.next.next = node6;
  System.out.println("Original list is:  12 18 172 62 632 192 19");
  System.out.print("Modified linked list is "
    + "(Using Iterative Implementation:) ");
  modifiedHead = rpll.reverseLinkedListInPairsIterative(head);
  displayLinkedList(modifiedHead);

  System.out.println("\n------2nd test-----");
  Node node12 = rpll.new Node(12);
  Node node22 = rpll.new Node(18);
  Node node32 = rpll.new Node(172);
  Node node42 = rpll.new Node(62);
  Node node52 = rpll.new Node(632);
  Node node62 = rpll.new Node(192);
  Node node72 = rpll.new Node(19);
  Node head2 = node12;
  node12.next = node22;
  node12.next.next = node32;
  node12.next.next.next = node42;
  node12.next.next.next.next = node52;
  node12.next.next.next.next.next = node62;
  node12.next.next.next.next.next.next = node72;
  System.out.println("Original list is:  12 18 172 62 632 192 19");
  System.out.print("Modified linked list is "
    + "(Using recursive Implementation:) ");
  modifiedHead = rpll.reverseLinkedListInPairsRecursive(head2);
  displayLinkedList(modifiedHead);
 }
}
==============Sample Output====================
 ------1st test-----
Original list is:  12 18 172 62 632 192 19
Modified linked list is (Using Iterative Implementation:) [ 18 12 62 172 192 632  ]
------2nd test-----
Original list is:  12 18 172 62 632 192 19
Modified linked list is (Using recursive Implementation:) [ 18 12 62 172 192 632 19  ]
=============================================

Find length of cycle in linked list in Java - Floyd cycle detection algorithm

Find length of cycle in a liked list is an application of Floyd cycle detection algorithm.In order to solve this problem, first we need to solve two problem in sequence - 1. find cycle in linked list in Java and 2. find beginning of cycle in linked list. Once we have found that beginning of  cycle, just traverse the cycle and manage a count until we reaches that starting node again. Refer above mentioned links for more details about cycle detection and finding beginning node of cycle. Below is the algorithm and sample code for finding length of cycle -
Algorithm:- 
1. First detecting cycle, then
2 .Find starting node of cycle
3. Find length of cycle (reach at beginning of beginning of cycle again)

Finding length of cycle:- 
static public int findLengthOfCycle(Node head) {
int length = 0;
if (head == null)
return 0;
Node fastReference = head;
Node slowReference = head;

/* Iterate linked list to detect cycle */
while (fastReference != null && slowReference != null) {
if (fastReference.next != null) {
/* fast reference - crosses 2 nodes at a time */
fastReference = fastReference.next.next;
}
if (slowReference != null) {
/* fast reference - cross 1 node at a time */
slowReference = slowReference.next;
}
if (fastReference!= null && slowReference!=null &&
fastReference.equals(slowReference)) {
   break;
}
}
/*
* Once cycle detected, place slowRef to start of linked list and
* traverse linked list one by one - they will meet again at start of
* node of cycle
*/
if (fastReference != null && slowReference != null) {
slowReference = head;
while (fastReference != slowReference) {
slowReference = slowReference.next;
fastReference = fastReference.next;
}


/* Find length of cycle - slowRef and fastRef referring same node */
slowReference = slowReference.next;
length++;
while (!slowReference.equals(fastReference)) {
slowReference = slowReference.next;
length++;
}
    }
return length;
}
Explanation:- While finding length of list, first we move slowReference and increment length. After that in while loop we traverse until again it meets fastReference.For each movement we increment length.

Below is the complete  sample program for finding length of cycle, if exist and return length of cycle.If cycle does not exist it return 0.
package com.devinline.linkedlist;

public class LengthOfCycleInCyclicSLL {

static Node head;

static public int findLengthOfCycle(Node head) {
int length = 0;
if (head == null)
return 0;
Node fastReference = head;
Node slowReference = head;

/* Iterate linked list to detect cycle */
while (fastReference != null && slowReference != null) {
if (fastReference.next != null) {
/* fast reference - crosses 2 nodes at a time */
fastReference = fastReference.next.next;
}
if (slowReference != null) {
/* fast reference - cross 1 node at a time */
slowReference = slowReference.next;
}
if (fastReference != null && slowReference != null
&& fastReference.equals(slowReference)) {
break;
}
}
/*
* Once cycle detected, place slowRef to start of linked list and
* traverse linked list one by one - they will meet again at start of
* node of cycle
*/
if (fastReference != null && slowReference != null) {
slowReference = head;
while (fastReference != slowReference) {
slowReference = slowReference.next;
fastReference = fastReference.next;
}

/* Find length of cycle - slowRef and fastRef referring same node */
slowReference = slowReference.next;
length++;
while (!slowReference.equals(fastReference)) {
slowReference = slowReference.next;
length++;
}
}
return length;
}

class Node {
public int data;
public Node next; // reference(handler) for next Node.

public Node(int data) {
this.data = data;
this.next = null;
}
}

public static void main(String[] args) {
LengthOfCycleInCyclicSLL cyc = new LengthOfCycleInCyclicSLL();
Node node1 = cyc.new Node(12);
head = node1;
Node node2 = cyc.new Node(18);
Node node3 = cyc.new Node(172);
Node node4 = cyc.new Node(62);
Node node5 = cyc.new Node(632);
Node node6 = cyc.new Node(192);
head.next = node2;
head.next.next = node3;
head.next.next.next = node4;
head.next.next.next.next = node5;
head.next.next.next.next.next = node6;
node6.next = node4; // cycle formed between node 6 and 4 - 62 is
// start
// of cycle

int lengthOfCycle = findLengthOfCycle(head);
System.out.println("Length of cycle is " + lengthOfCycle);

}

}
===Sample output====
Length of cycle is 3
=================

May 16, 2014

How to merge two sorted linked list in third linked list - Iterative and recursive approach

Problem Statement :- Given two sorted linked list, merge two linked list and form third sorted linked list containing all elements of given liked list. Solve using non-recursive and recursive approach.
/*  Merge two sorted linked lists and form third sorted linked list
*List1: 4-->5-->12 -->24 -->83
*List2: 8-->9-->14 -->21 -->31 -->132 -->136
* Result(Sorted list) : 4->5->8->9->12->14->21->24->31->83->132->136 
*/

Non-recursive approach(Iterative):-  

Iterative Since all elements are sorted in both linked list, we can traverse both liked list and by comparing element of both linked list we can decide which is smaller and put that in result linked list and repeat this until all elements are covered in one of the list and after that just copy all elements from second list.
Algorithm:-  Lets consider head1 and head2 are referring first node of two linked list.
1. Traverse linked list List1 and List2 until head1 is null or head 2 is null.
2. Compare data of first node of both list - add node with lesser value into result linked list and increment head of that linked list.
3. Repeat step 2 and move corresponding head.
4. Once head of one of list has reached at end of list, just copy all elements from another linked list into result list.

Sample code to merge two sorted linked list into one linked list (Non-recursive approach):-
private Node mergeSortedLinkedListIterative(Node head1, Node head2) {
Node resultHead = null;
/* Traverse both list until reaches at end of any one of list */
while (head1 != null && head2 != null) {
if (head2.data < head1.data) {
resultHead = createAndAppendNodeInResultList(resultHead,
head2.data);
head2 = head2.next;
} else {
resultHead = createAndAppendNodeInResultList(resultHead,
head1.data);
head1 = head1.next;
}
}
// Copy remaining linked list data into result list
if (head1 != null) {
while (head1 != null) {
createAndAppendNodeInResultList(resultHead, head1.data);
head1 = head1.next;
}
} else if (head2 != null) {
while (head2 != null) {
createAndAppendNodeInResultList(resultHead, head2.data);
head2 = head2.next;
}
}
return resultHead;
}
Explanation:- In while loop, both list is traversed until reaches at end of one list and compare which list node has lesser value element, if head1 refer to lesser value node, it is added in result list and head1 moves to next node. Similarly, if head2 node refer lesser value it is added and moves to next node. After while loop is exit, which ever list has more elements to be traversed is copied to result linked list.
Time and space complexity :- Since each element is traversed only once so time complexity is order of O(p+q), p and q are length of linked list. Space complexity is constant O(p+q) , length of result list.

Using recursion:-

Algorithm:- 1. Check head of both list , if one of them is null returns others, because that list does not have more elements.
2. Next, if both are non- null, check for node with lesser value and assume that node as head of result liked list. Call same method recursively with next element of that list. Do the same if other list has lesser values node.
3. Return head of result linked list.

Sample code to merge two sorted linked list into one linked list (Recursive approach):-
private Node mergeSortedLinkedListRecursive(Node head1, Node head2) {
Node returnNode = null;
if (head1 == null && head2 != null)
return head2;
if (head2 == null && head1 != null)
return head1;

if (head1.data < head2.data) {
returnNode = head1;
returnNode.next = mergeSortedLinkedListRecursive(head1.next, head2);
}
if (head1.data > head2.data) {
returnNode = head2;
returnNode.next = mergeSortedLinkedListRecursive(head1, head2.next);
}
return returnNode;
}

Time and space complexity :- Since each element is traversed only once so time complexity is order of O(p+q), p and q are length of linked list. Space complexity is constant O(p+q) , length of result list.
Below is complete sample program to merge two sorted linked list in third linked list(Both non-recursive and recursive approach) :-
package com.devinline.linkedlist;

public class MergeTwoSortedLinkedList {

private Node mergeSortedLinkedListIterative(Node head1, Node head2) {
Node resultHead = null;
/* Traverse both list until reaches at end of one list */
while (head1 != null && head2 != null) {
if (head2.data < head1.data) {
resultHead = createAndAppendNodeInResultList(resultHead,
head2.data);
head2 = head2.next;
} else {
resultHead = createAndAppendNodeInResultList(resultHead,
head1.data);
head1 = head1.next;
}
}
// Copy remaining linked list data into result list
if (head1 != null) {
while (head1 != null) {
resultHead = createAndAppendNodeInResultList(resultHead,
head1.data);
head1 = head1.next;
}
} else if (head2 != null) {
while (head2 != null) {
resultHead = createAndAppendNodeInResultList(resultHead,
head2.data);
head2 = head2.next;
}
}
return resultHead;
}

private Node mergeSortedLinkedListRecursive(Node head1, Node head2) {
Node returnNode = null;
if (head1 == null && head2 != null)
return head2;
if (head2 == null && head1 != null)
return head1;

if (head1.data < head2.data) {
returnNode = head1;
returnNode.next = mergeSortedLinkedListRecursive(head1.next, head2);
}
if (head1.data > head2.data) {
returnNode = head2;
returnNode.next = mergeSortedLinkedListRecursive(head1, head2.next);
}
return returnNode;
}

private Node createAndAppendNodeInResultList(Node head, int data) {
return head = insertLast(head, data);
}

private Node createNewNode(int data) {
return new Node(data);
}

/* Iterate linked list, reach at end and add new node */
private Node insertLast(Node head, int data) {
Node newNode = createNewNode(data);
Node current = head;
if (head == null) {
head = newNode;
} else {
while (current.next != null) {
current = current.next;
}
current.next = newNode;
newNode.next = null;
}
return head;
}

/* Display data of nodes/iterate linked list */
private void diplayList(Node head) {
Node current = head;
System.out.print(" [ ");
if (head != null) {
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.print(" ]");
} else {
System.out.println("Linked list is empty.");
}

}

class Node {
public int data;
public Node next;

public Node(int data) {
this.data = data;
this.next = null;
}
}

public static void main(String[] args) {
Node head1 = null;
Node head2 = null;
MergeTwoSortedLinkedList mll = new MergeTwoSortedLinkedList();
/* First linked list fomation */
Node node1 = mll.new Node(4);
head1 = node1;
Node node2 = mll.new Node(5);
Node node3 = mll.new Node(12);
Node node4 = mll.new Node(24);
Node node5 = mll.new Node(83);
head1.next = node2;
head1.next.next = node3;
head1.next.next.next = node4;
head1.next.next.next.next = node5;

/* Second linked list fomation */
Node node12 = mll.new Node(8);
head2 = node12;
Node node22 = mll.new Node(9);
Node node32 = mll.new Node(14);
Node node42 = mll.new Node(21);
Node node52 = mll.new Node(31);
Node node62 = mll.new Node(132);
Node node72 = mll.new Node(136);
head2.next = node22;
head2.next.next = node32;
head2.next.next.next = node42;
head2.next.next.next.next = node52;
head2.next.next.next.next.next = node62;
head2.next.next.next.next.next.next = node72;

System.out.println("linked list-1 [4-->5-->12 -->24 -->83]\n"
+ "linked list-2 [8-->9-->14 --> 21 --> 31 -->132-->136]\n");
System.out.print("Merged linkedlist using iterative appraoch : ");
mll.diplayList(mll.mergeSortedLinkedListIterative(head1, head2));

/* mark head1 = null */
Node head3 = null;
System.out.print("\n\nMerged linkedlist iterative appraoch- "
+ "with only List2 has values: ");
mll.diplayList(mll.mergeSortedLinkedListIterative(head3, head2));

System.out.print("\n\nMerged linkedlist recursive appraoch- "
+ "with only List1 has values: ");
mll.diplayList(mll.mergeSortedLinkedListRecursive(head1, head3));

System.out.print("\n\nMerged linkedlist using recursive appraoch : ");
mll.diplayList(mll.mergeSortedLinkedListRecursive(head1, head2));

}
}
===========Sample output===============
linked list-1 [4-->5-->12 -->24 -->83]
linked list-2 [8-->9-->14 --> 21 --> 31 -->132-->136]

Merged linkedlist using iterative appraoch :  [ 4 5 8 9 12 14 21 24 31 83 132 136  ]

Merged linkedlist iterative appraoch- with only List2 has values:  [ 8 9 14 21 31 132 136  ]

Merged linkedlist recursive appraoch- with only List1 has values:  [ 4 5 12 24 83  ]

Merged linkedlist using recursive appraoch :  [ 4 5 8 9 12 14 21 24 31 83 132 136  ]
=======================================