Sorted Linked List To Balanced BST

http://www.geeksforgeeks.org/archives/17063

Construct binary tree given its inorder and preorder traversal

Construction of Binary tree given its inorder and preorder traversal.

 public static Node construct(String preorder, String inorder, int start, int end, int [] preorderIndex)
 {
  if(start > end)
   return null;
  
  Node root = new Node(preorder.charAt(preorderIndex[0]));
  
  ++preorderIndex[0];
  
  int inorderIndex = inorder.indexOf(""+root.data);
  
  root.left  = construct(preorder, inorder, start, inorderIndex - 1, preorderIndex);
  root.right = construct(preorder, inorder, inorderIndex + 1, end, preorderIndex);
  
  return root;
 }
  
 public static void main(String[] args) {
  
  String preorder = "ABCDEFG";
  String inorder  = "GFEDCBA";
  
  // We use this as a reference object, so that we pick the correct value from preorder array during
  // recursion. This could be done by having a static variable as well.
  int [] preorderIndex = new int[1];
  
  Node root = CodeSamples.construct(preorder, inorder, 0, preorder.length() - 1, preorderIndex);
                // Verify if it build correctly
  BinaryTree.preorderTraversal(root);
  System.out.println();
  BinaryTree.inorderTraversal(root);
  
 }

For explanation of the approach and other ways of doing it, visit this link: http://www.geeksforgeeks.org/archives/6633

Adding two linked lists

Given 2 singly linked lists which have single digit data, add the two lists and return a new list.

For e.g.

list1: 4->5->5->9->8
list2:      2->3->1->1

Output should be: 4->7->9->0->9

Approach 1: One of the approach can be to reverse both the linked list and then add node by node. In that case you will need to reverse the output list as well.

Approach 2: The other approach is to put the linked lists in the stack. This avoids the need to reverse the lists.

 
public static Node addLinkedLists(Node head1, Node head2)
 {
  if(head1 == null)
   return head2 != null ? head2 : null;
  
  if(head2 == null)
   return head1 != null ? head1 : null;
  
  Stack<node> s1 = new Stack<node>();
  Stack<node> s2 = new Stack<node>();
  Stack<node> s3 = new Stack<node>();
  
  Node list1 = head1;
  Node list2 = head2;
  
  while(list1 != null)
  {
   s1.push(list1);
   list1 = list1.next;
  }
  
  while(list2 != null)
  {
   s2.push(list2);
   list2 = list2.next;
  }
  
  int carry = 0;
  
  while(!s1.empty() &amp;&amp; !s2.empty())
  {
   int total = carry + s1.pop().data + s2.pop().data;
   Node n = new Node(total%10);
   s3.push(n);
   carry = total/10;
  }
  
  while(!s1.empty())
  {
   int total = carry + s1.pop().data;
   Node n = new Node(total%10);
   s3.push(n);
   carry = total/10;
  }
  
  while(!s2.empty())
  {
   int total = carry + s2.pop().data;
   Node n = new Node(total%10);
   s3.push(n);
   carry = total/10;
  }
  
  Node result = s3.pop();
  Node retHead = result;
  
  while(!s3.empty())
  {
   Node n = s3.pop();
   result.next = n;
   result = n;
  }
  
  return retHead;
 }

Both approaches have similar run time complexity but the stack based approach requires more space.

Deep Copy of a doubly linked list where previous pointers point to any arbitrary node in the list

Given a doubly linked list which looks as follows, make a deep copy of the linked list and return the head of the new linked list.

Deep copy implies that we have to make an exact copy of each node in the original list and assign the pointers same as that of the original list.

Since the previous pointers point to any arbitrary node in the list, we need to keep an association between nodes of the old linked list and the new liked list.

Here are 2 ways I can think of doing this. Both of them are O(n) in time but method 1 takes O(n) space.

Method 1:

In this method we save the association in the form of an hashtable.

public static Node deepCopy(Node head)
 {
  if(head == null)
   return null;
  
  Node oldHead = head;
  
  // Traverse the original doubly linked list and create a new 
  // singly linked list 
  // When creating the new linked list save the association between 
  // corresponding old and new nodes in a hashtable
  // For e.g. original: 1->2->3->4
  //          new:   1'->2'->3'->4'
  // hashtable contains mapping of [1->1'], [2->2'],..
  
  Hashtable<node, node> oldToNewNodeMap = new Hashtable<node, node>();
  
  // Create the new head
  Node newHead = new Node(oldHead.data+"'");
  oldToNewNodeMap.put(oldHead, newHead);
  
  Node tmp = newHead;
  
  oldHead = oldHead.next;
  
  // Create rest of the singly linked list with next pointers
  while(oldHead != null)
  {
   Node newNode = new Node(oldHead.data+"'");
   oldToNewNodeMap.put(oldHead, newNode);
   tmp.next = newNode;
   
   oldHead = oldHead.next;
   tmp = tmp.next;
  }
  
  tmp = newHead;
  oldHead = head;
  
  // Now assign the prev pointers
  while(oldHead != null)
  {
   tmp.prev = oldToNewNodeMap.get(oldHead.prev);
   
   oldHead = oldHead.next;
   tmp = tmp.next;
  }
  
  return newHead;
 }

Method 2:

In this method we modify the original linked list for the time being to store the association and then revert it back to the original linked list.

public static Node deepCopy(Node head)
 {
  if(head == null)
   return null;
  
  // Rather than using a hastable create new association in 
  // the following way:
  // Create new nodes and insert it into the original linked list 
  // as follows
  // For e.g. 1->1'->2->2'->3->3'->4->4' where 1', 2',.. are 
  // the new nodes created
  
  Node curNode = head;
  
  while(curNode != null)
  {
   Node newNode = new Node(curNode.data+"'");
   
   // New node's next points to current node's next
   // New node's previous continues to point to current node's prev
   newNode.next = curNode.next;
   newNode.prev = curNode.prev;

   // Current node should now point to the new node
   Node next = curNode.next;
   curNode.next = newNode;
   
   // Advance to the original list's node
   curNode = next;
  }
  
  // Now assign correct previous pointer for alternate node (alternate  
  // nodes are the new nodes but they currently point to the prev
  // of original nodes)
  curNode = head;
  boolean odd = true;
  while(curNode != null)
  {
   if(!odd)
   {
    curNode.prev = curNode.prev.next;
   }
   
   odd = !odd;
   curNode = curNode.next;
  }
  
  // Now break the linked list into original and new linked list
  curNode = head;
  Node newHead = curNode.next;
  
  while(curNode != null && curNode.next != null)
  {
   Node p = curNode;
   Node n = curNode.next.next;
   curNode = curNode.next;
   p.next = n;
  }
  
  return newHead;
 }

As you can see method 1 traverses the list thrice but requires less space whereas method 1 traverses the list twice but requires extra space.

Swap nodes of a linked list

For e.g:
Input: 1->2->3->4->5->6
Output: 2->1->4->3->6->5


There are 2 ways I could think by which we can solve this. Both methods take O(n) time.
Method 2 however is more elegant.

Method 1:

public static Node swapNodes(Node head)
{ 
  Node c = head;
  Node p = c;
  
  boolean headSet = false;
  
  while(c != null && c.next != null)
  {
   Node n = c.next; 
   c.next = n.next;
   n.next = c;

   if(!headSet)
   {
    head = n;
    headSet = true;
   }
   else
   {
    p.next = n;
    p = c;
   }
   
   c = c.next;
  }
  
  return head;
}

Method 2:

public static Node swapNodes(Node head)
 { 
  Node c = head;
  
  // Create a dummy node before the head node
  Node dummy = new Node();
  dummy.next = head;

  Node p = dummy;
  
  while(c != null && c.next != null)
  {
   Node n = c.next; 
   c.next = n.next;
   n.next = c;

   p.next = n;
   p = c;
   
   c = c.next;
  }
  
  return dummy.next;
 }