Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Divide Linked List In Two

Easy
0/40
Average time to solve is 20m
profile
Contributed by
20 upvotes
Asked in companies
JP MorganDirectiAmazon

Problem statement

You have been given a singly Linked List of integers. Your task is to divide this list into two smaller singly-linked lists in which the nodes appear in alternating fashion from the original list.

For example:
If the given linked list is 1 -> 2 -> 3 -> 4 -> 5 -> NULL

The first sub-list is 1 -> 3 -> 5 -> NULL.
The second sub-list is 2 -> 4 -> NULL.

If it is impossible to make any of the two smaller sub-lists, return an empty list i.e. NULL.

Detailed explanation ( Input/output format, Notes, Images )
Constraints :
1 <= T <= 10^2
0 <= LEN <= 5*10^3
1 <= data <= 10^9

Where LEN is the number of nodes in the Linked List.

Time Limit: 1 sec
Sample Input 1 :
2
1 2 3 4 5 -1
1 2 -1
Sample Output 1 :
1 3 5 -1
2 4 -1
1 -1
2 -1
Explanation For Sample Input 1 :
For the first test case, we have 1, 3, 5 in the first and 2, 4 in the second linked list.

For the second test case, we have 1 in the first and 2 in the second linked list.
Sample Input 2 :
2
1 2 3 -1
1 -1
Sample Output 2 :
1 3 -1
2 -1
1 -1
-1
Full screen
Console