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

by

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;
}
}

view raw
MergeTwoListAtAlternatePositions.java
hosted with ❤ by GitHub


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

Related Posts: