# 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:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 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
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.