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.
Learn more about bidirectional 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