0

Trying to self-learn Linked Lists, I stumbled upon a merging algorithm:

Node MergeLists(Node node1, node2)
{
    if(node1 == null)
      return node2;
   else (node2 == null)
      return node1;

   Node head;
   if(node1.data < node2.data)
   {
      head = node1;
      node1 = node1.next;
   else
   {
      head = node2;
      node2 = node2.next;
   }

   Node current = head;
   while((node1 != null) ||( node2 != null))
   {
      if(node1 == null) {
         current.next = node2;
         return head;
      }
      else if (node2 == null) {
         current.next = node1;
         return head;
      }

      if(node1.data < node2.data)
      {
          current.next = node1;
          current = current.next;
          node1 = node1.next;
      }
      else
      {
          current.next = node2;
          current = current.next;
          node2 = node2.next;
      }
   }
   current.next = NULL // needed to complete the tail of the merged list
   return head;

}

courtesy of : https://stackoverflow.com/a/13886252/6630382

While I understand the logic for the most part, I am confused about: 1. Why do we need to declare "Node current"? Unless I am forgetting something about aliasing, wouldn't we be okay just using the Node head all the way through?

  1. Is there some sort of prerequisite needed for the merged list? Would we have to pre-define a list of size list1 + list2 or would this just build the list from scratch?

Thank you so much!

Community
  • 1
  • 1
javanewbie
  • 117
  • 1
  • 9
  • 4
    1. you need **current** because a LinkedList is represented by its first element (or **head**), if you use **head** and change it, you won't be able to return the list; 2. in LinkedList merging, you are manipulating node objects, you only change their relative relationship rather than creating and deleting objects. A good practice for coding reviewing is mentally stepping through the code. – solosodium Aug 18 '16 at 15:16
  • @solosodium wow thank you so much that made a lot of sense :). So my interpretation is that while the essential Node object that head and current point at changes as current goes down the lists, head will continue to point at the first node, albeit even as the first node changes. This seems to be a common practice amongst all of the data structures I am running into- the use of some "pointer" to iterate through the lists. – javanewbie Aug 18 '16 at 15:25

0 Answers0