Flatten a multi-level linked list


  • 2
    A

    Given a linked list with both next and down pointers, flatten the list into a single linked list.
    For example, given

    A---B---C----D--E---F--NULL
                  |
                  G---H---I---J--NULL
                          |
                         K---L--NULL
    

    should become A-B-C-G-H-K-L-I-J-D-E-F-NULL


  • 0

    @ankanr Is it possible some of the inner modes to have down pointers or only the first nodes posess this property? How many levels comprise the list ?
    Was there a contraint on the number nodes in each level?

    Also what happens in the following example : ?

    
    A---B----C---D---E----F---S--M---N
    |
    G---H---I----J---NULL
    |
    K--L--P--NULL
    |
    S--T--NULL

  • 0
    A

    any node can have down pointer, including the inner node.

    also, the down pointer can be valid or null. similarly the next pointer can be valid or null.

    in you case, the solution becomes

    A-G-K-S-T-L-P-H-I-J-B-C-D-E-F-S-M-N-NULL


  • 1

    @ankankr Thank you very much! Just another question : Do you think your example is correct?
    In your example you iterate a part of the first level of the list (A,B,C) , but in my example you iterate in deep A-G-K-S, something like dfs
    Isn't the answer of the given example :
    A-G-K-L-H-I-J-B-C-D-E-F
    Can you calrify the rule of list flattening?

    @ankankr said in Flatten a multi-level linked list:

    Given a linked list with both next and down pointers, flatten the list into a single linked list.
    For example, given
    A---B---C----D--E---F--NULL
    |
    G---H---I---J--NULL
    |
    K---L--NULL

    should become A-B-C-G-H-K-L-I-J-D-E-F-NULL


  • 0

    @elmirap I agree with you.


  • 0
    A

    Thanks for pointing out. My example is incorrect because of formatting issue. I intended to have down pointer from C in the first level, then H in the second level, but it did not show up correctly when posted. Hope that clarifies.


  • 0

    @ankankr You can edit your original post to fix the issues.


  • 0

    @babhishek21 This is the original example.

     A---B---C----D--E---F--NULL
             |
             G---H---I---J--NULL
                 |
                 K---L--NULL
    
     should become A-B-C-G-H-K-L-I-J-D-E-F-NULL

  • 0

    @elmirap So how does one establish which node comes first in the flattening? (:yum:)
    For the example

     A---B---C----D--E---F--NULL
             |
             G---H---I---J--NULL
                 |
                 K---L--NULL
    
     should become A-B-C-G-H-K-L-I-J-D-E-F-NULL
    

    it looks like that once we reach the lowest/deepest level, the nodes of a deeper level will always hold priority over nodes of a shallower level. Am I right in thinking so?


  • 0

    @babhishek21 yes, I think the same. We traverse the list taking always the down link first .If down list doesn't exist we will move to the right


  • 0

    @ankankr What will be the result of this input? Thank you

     A---B---C---D--E---F--NULL
             |   |
             G---H---I---J--NULL
                 |   |
                 K---L--NULL

  • 1

    I think the idea is to simply do a DFS with the down pointer begin processed first.

    @1337c0d3r @elmirap Do you think this question is worthy of being published?


  • 0

    @babhishek21 Yes definitely. This is a classic problem, would love to add it to the library. Let's communicate via chat.


  • 1
    N

    I think this problem is similar to (maybe the same as) pre-order traversal of binary tree.


  • 0
    M

    This is version of the pseudocode i would use to solve the problem

    class Node():
        def __init__():
            self.val=-1
            self.next=None
            self.down=None
            
    
    def solve(head):
        stack=[]
        dummy=new Node()
        dummy.next=head
        while(head!=None or len(stack)!=0):
            if(head.down!=None):
                if(head.next):
                    stack.append(head.next)
                head.next=head.down
                head=head.next
            elif(head.next!=None):
                head=head.next
            else:
                if(len(stack)!=0):
                    head.next=stack.pop()
                    head=head.next
        return dummy.next

  • 0

    @elmirap I am also curious about the case when input multi-level linked list has multiple down pointers referencing the lower level. But I guess in this case, only the first down pointer is useful as it has to point to the head of the lower level list. If this is the case, then having multiple down pointers at the same level only adds complexity to the logic in the code, I think. Anyway, it will need a good definition of what flatten means to well form a good problem.


  • 0

    Assuming the desired flattened liked list is to always move lower level list up right after bifurcation node, and attach the remaining list after the flattened link, then we can do DFS to locate bifurcation node on each level and modify its next pointer to point to the flattened list of lower level. Finally, we need to set down pointer in each node to NULL since the returned list must be flattened.

    struct Node { // define multi-level linked list node
      Node* next, *down;
      Node():next(NULL), down(NULL) { }
    };
    
    Node* flatten(Node* head) {
        if (!head) return NULL;
        Node* cur = head;
        while (cur && !cur->down) cur = cur->next; // find bifurcation node
        if (!cur) return head; // if no bifurcation, just return 
        Node* nxt = cur->next; // record the remaining list after bifurcation node 
        cur->next = flatten(cur->down); // flatten lower level list
        cur->down = NULL; // flatten bifurcation node
        while (cur->next) {  // find the new tail after flatten and set down to NULL
            cur->down = NULL;
            cur = cur->next;
        }
        cur->next = nxt; // attach tail to the remaining list
        return head;
    }
    

  • 0
    S

    @zzg_zzm said in Flatten a multi-level linked list:

    flatten(cur->down)

    cur->next=nxt will not work.
    You should flatten nxt!


  • 1
    /*
    class ListNode {
        int val;
        ListNode next;
        ListNode down;
        ListNode(int val) {
            this.val = val;
        }
    }
    /*
     * My Java solution using recursion and DFS
     * I simply assume there is only one node in the upper level who can get access to the lower level.
     * If not, you can simply add a flag to detect whether the lower level is been flattened or not. 
     */
    public ListNode flattenList(ListNode head) {
        ListNode running = head;
        while (running != null) {
            if (running.down != null) {
                ListNode next = running.next;
                ListNode fromBellow = flattenList(running.down);
                running.next = fromBellow;
                running.down = null;
                while (running.next != null) {
                    running = running.next;
                }
                running.next = next;
            }
            if (running.next != null) {
                running = running.next;
            } else {
                break;
            }
        }
        return head;
    }

  • 1
    H

    @ankankr Pardon me if I got it wrong. Based on your examples, the problem looks equivalent to pre-order traversal of the list to me. Correct me if I am mistaken.

    // Class to represent a node
        class Node{
            char data;
            Node next, down;
    
            public Node(char data) {
                this.data = data;
                this.next = null;
                this.down = null;
            }
        }
    
        // Method to flatten the list
        String flattenList(Node head){
            if (head == null)
                return "";
    
            // Below lines are written in this manner to increase the code readability. 
            // One may choose to use StringBuilder instead of String to optimize it.
            String result = "";
            result += head.data + " ";
            result += flattenList(head.down);
            result += flattenList(head.next);
            return result;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.