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.