Alternate Splitting of a given Linked List

Objective: Given a singly linked list, split it into two linked lists. These linked lists will contain the alternate nodes from the given linked list.

Example:

Alternate Splitting of a given Linked List

Approach:

  • Make two pointers(headA and headB) and set it to head and next just to fix the headers for the new linked list.
  • Make Node currNode = head and Node t = currNode.next.
  • Do the traversal of the linked list.
  • Make next = t.next and t.next = currNode.next.next. (Splitting step).
  • Keep checking whether next!=null && currNode.next.next!=null.

Complete Code:

public class AternateSplit {
public static Node head = null;
public static Node headA = null; //linked List 1
public static Node headB = null; // Linked List 2
public void Altersplit() {
Node currNode = head;
if (currNode == null || currNode.next == null) {
return; // we have nothing to split, return
}
headA = currNode; //set the head for first Linked List
headB = currNode.next; //set the head for second Linked List
while (currNode != null && currNode.next != null) {
Node t = currNode.next;
currNode.next = t.next; // set the next node for first linked list
// Now check if next node is available for second Linked List
if (currNode.next != null && currNode.next.next != null) {
t.next = currNode.next.next; // set the next node for second linked list
} else { // we have reached to the end
t.next = null;
return;
}
currNode = currNode.next; // keep moving forward
}
}
public void print(Node x) {
System.out.println("");
Node curr = x;
while (curr != null) {
System.out.print("->" + curr.data);
curr = curr.next;
}
}
public static void main(String[] args) throws java.lang.Exception {
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(1);
head.next.next.next = new Node(2);
head.next.next.next.next = new Node(1);
head.next.next.next.next.next = new Node(2);
AternateSplit i = new AternateSplit();
i.print(head);
i.Altersplit();
i.print(headA);
i.print(headB);
}
}
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
next = null;
}
}

view raw
AternateSplit.java
hosted with ❤ by GitHub


Output:

->1->2->1->2->1->2
->1->1->1
->2->2->2