0

You are given a linked list containing 'n' 'head' nodes, where every node in the linked list contains two pointers:

(1) ‘next’ which points to the next node in the list

(2) ‘child’ pointer to a linked list where the current node is the head.

Each of these child linked lists is in sorted order and connected by 'child' pointer.

Your task is to flatten this linked such that all nodes appear in a single layer or level in a 'sorted order'.

This is the question I am trying to solve however I am only able flatten the first child list after that my program exits for some reason.enter image description here

This is my current code:-

public class Solution {
    public static Node flattenLinkedList(Node head) {
        //Write your code here
        if(head == null||head.next==null){
            return head;
        }
        Node childptr = head.child;
        Node listptr = head;
        Node temp = listptr.next;
        while(temp!=null){
            // Node next = childptr.child;
            childptr.next = listptr.next;
            listptr.next = childptr;
            listptr = listptr.next;
            
            childptr = childptr.child;
            if(childptr==null){
                childptr = temp.child;
                listptr = temp;
                temp = temp.next;
            }
        }
        return head;
    }
}

enter image description here

This is the output I am getting.

4
  • Don't tag with dsa (read the tag description) Commented Feb 9, 2024 at 5:17
  • 1
    You're quite far from a correct solution. Use the example and design the algorithm first. You have a collection of sorted lists and must produce a single completely sorted result. This means you'll need to merge all input lists: repeatedly pop the smallest head node from its list and append it to the result. How can you accomplish that? Commented Feb 9, 2024 at 5:41
  • I agree with Gene. You perform node mutations without checking whether the connected nodes are in the expected order. Your code never looks at the value of a node, which is of course necessary to guarantee that you're constructing a list that is sorted. You return head, but head is not necessarily the node with the least value (only child-lists are known to be sorted, the next-list is not necessary sorted). Back to the drawing board. Commented Feb 9, 2024 at 6:40
  • BTW, what is "a single layer or level". Is that a list connected by next or by child? Commented Feb 9, 2024 at 17:44

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.