# Merge a Linked list into another Linked List at Alternate Positions.

Objective: Given two linked lists, merge one list into another at alternate positions, if second link list has extra nodes, print them as well

Example:

```5 -> 10 -> 15 -> 20 ->25 -> null
3 -> 6 ->9 -> 12 ->15 ->18 ->21 -> null

Output :
5 -> 3 -> 10 -> 6 ->15 -> 9 -> 20 -> 12 -> 25 ->15 -> null
Remaining List : 18 -> 21 -> null
```

Approach:

• Say Node A and Node B are the starting of two linked list.
• Take Node temp = A ( store the head of the link list one).
• Take Node A1 = A.next and Node B1 = B.next;
• Make A.next points to the B.
• Make B.next = A1. (at this point B is inserted between A and A1).
• Do the above two steps till one of the list burns out.
• Print the list using temp node.
• Print the remaining list in B, B will be pointing to the head of the remaning list.

Complete Code:

 public class MergeTwoListAtAlternatePositions { public static void main(String[] args) throws java.lang.Exception { Node a = new Node(5); a.next = new Node(10); a.next.next = new Node(15); a.next.next.next = new Node(20); a.next.next.next.next = new Node(25); MergeTwoListAtAlternatePositions i = new MergeTwoListAtAlternatePositions(); i.display(a); System.out.println(""); Node b = new Node(3); b.next = new Node(6); b.next.next = new Node(9); b.next.next.next = new Node(12); b.next.next.next.next = new Node(15); b.next.next.next.next.next = new Node(18); i.display(b); i.alterMerge(a, b); } public void display(Node head) { Node currNode = head; while (currNode != null) { System.out.print("->" + currNode.data); currNode = currNode.next; } } public void alterMerge(Node a, Node b) { Node temp = a;// it will be needed to get the head of the new list while (a != null && b != null) { Node a1 = a.next; Node b1 = b.next; a.next = b; b.next = a1; a = a1; b = b1; } System.out.println("\nAlternate Mergred List"); display(temp); System.out.println("\nRemaining Second List"); display(b);// b will be pointing to the ahead of the remaining list } } class Node { public int data; public Node next; public Node(int data) { this.data = data; this.next = null; } }

Output:

```->5->10->15->20->25
->3->6->9->12->15->18
Alternate Mergred List
->5->3->10->6->15->9->20->12->25->15
Remaining Second List
->18
```