Flatten a Linked List in Java

This morning I read the article Kode Vicious Kabin Fever on Viewpoints in the latest copy of the Communications magazine from the ACM. I enjoyed reading the article. All of the points with the only exception to exercise, due to winter and the COVID-19 pandemic, with very few additions, are what I have been doing for over a decade. If you have time and are able to access the article, it contains good advice and it can be read in a few minutes.

Most problems in this blog come from companies such as HackerRank or LeetCode just to mention a few. In this case, the problem came up while chatting with a software engineer. I have developed the requirements as accurate as I can recall. I will be using the Java programming language on a Windows 10 machine using the VSCode IDE. Of course you can generate a solution in a different platform using a different IDE.

I will try to follow the same organization as I would when solving a problem from LeetCode. I was not able to find this problem there. If you know of this problem with a different name, please let me know. Would like to see how much the requirements and implementation differ from what I have here.

Given a singly linked list with one or more alternates,
return a flattened linked list by just modifying links
to the primary linked list.

|2|->|X|->|6|->|8|->}9|-+
      |                 =
	  |
	  +->|3|->|4|->|5|-+
	                   =

output: 2->3->4->5->6->8->9-+
                            =						
Note:

o You must define the Node data structure.

We are given a singly linked list which can contain special nodes with alternate linked lists. Our task is to define the data structure / class to specify the nodes in the linked lists and the code to flatten them into a single linked list. You need modify the original linked list.

In our example, when we reach the second node we must detect that this is node flags an alternate linked list. The alternate linked list contains three nodes. The output shows how the contents of the alternate linked list replaced the special node with the contents of the alternate linked list.

/**
 * Class for linked list nodes
 */
class LLNode {

}

We need to define the members and methods we see fit to solve the problem at hand.

public LLNode flatten(LLNode head) {

}

The signature of the method we need to implement is provided.

2,null,6,8,9
3,4,5
main <<< strArr: [2, null, 6, 8, 9]
main <<<      B: 1
main <<<   arrs:
[3, 4, 5]
main <<< head: 2->X->6->8->9
main <<< head: 2->3->4->5->6->8->9


null,2,6,8,9
3,4,5
main <<< strArr: [null, 2, 6, 8, 9]
main <<<      B: 1
main <<<   arrs:
[3, 4, 5]
main <<< head: X->2->6->8->9
main <<< head: 3->4->5->2->6->8->9


null,2,6,8,9,null
1,2,3,4
2,4,6,8,10
main <<< strArr: [null, 2, 6, 8, 9, null]
main <<<      B: 2
main <<<   arrs:
[1, 2, 3, 4]
[2, 4, 6, 8, 10]
main <<< head: X->2->6->8->9->X
main <<< head: 1->2->3->4->2->6->8->9->2->4->6->8->10


5,null,10,null,19,null,28,null
7,8,30
20
22,50
35,40,45
main <<< strArr: [5, null, 10, null, 19, null, 28, null]
main <<<      B: 4
main <<<   arrs:
[7, 8, 30]
[20]
[22, 50]
[35, 40, 45]
main <<< head: 5->X->10->X->19->X->28->X
main <<< head: 5->7->8->30->10->20->19->22->50->28->35->40->45

We have four test cases. Let’s figure out what our test code is doing in order to collect the data we need to create the linked list that we will use as argument to the method we need to implement.

The first input line contains a list of integers. These integers are to be used as values in the nodes of the primary linked list. Please note that the null indicates that the space is reserved for an alternate linked list.

The second line contains the values for the first alternate linked list. Since in the first example we only have a single null, we only have a single alternate linked list. Other examples may contain multiple alternate linked lists. If so, each of the following input lines are associated with an additional alternate linked list.

It seems that our test code reads the first input line and places the values in a String[] array. It appears to count the number of nodes that have associated an alternate linked list. The variable B indicates that in the first example we have a single alternate linked list. In the fourth example we have four alternate linked lists.

Our test code the displays the values for the alternate linked lists which have been placed in an int[][] array.

It seems that the test code displays the linked list before we call our flatten() method. The linked list is then displayed after it has been flatten.

It is simple to check the results by making sure each node shown with an X has been replaced with the associated alternate linked list.

OK, at this time please take a few moments to figure out what needs to be done. We first need to create the LLNode class followed by the flatten() method. Go ahead and take as much time as needed…

… OK, seems we are ready to move on.

/**
 * Class for linked list nodes
 */
class LLNode {

    // **** class members ****
    public int val;
    public LLNode next;
    public LLNode alt;

    /**
     * Constructor(s)
     */
    public LLNode(int val) {
        this.val = val;
    }

    public LLNode() {
    }

    /**
     * Convert to string
     */
    @Override
    public String toString() {
        return "" + this.val;
    }
}

We have a typical node for a singly linked list. We have just added the alt member to hold the contents of the alternate linked list associated with this node.

We have two constructors and a toString() method. The last method was only used to display the linked list in our test code.

    /**
     * Test scaffold
     * 
     * !!! NOT PART OF SOLUTION !!!
     * 
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {

        // **** initialization ****
        int B = 0;

        // **** open a buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read the values for the main linked list ****
        String[] strArr = br.readLine().trim().split(",");

        // ???? ????
        System.out.println("main <<< strArr: " + Arrays.toString(strArr));

        // **** determine the number of branches ****
        for (int i = 0; i < strArr.length; i++) {
            if (strArr[i].equals("null"))
                B++;
        }

        // ???? ????
        System.out.println("main <<<      B: " + B);

        // **** read values for branches ****
        int[][] arrs = new int[B][];
        for (int b = 0; b < B; b++) {
            arrs[b] = Arrays.stream(br.readLine().trim().split(","))
                            .mapToInt(Integer::parseInt)
                            .toArray();
        }

        // ???? ????
        System.out.println("main <<<   arrs:");
        for (int i = 0; i < B; i++)
            System.out.println(Arrays.toString(arrs[i]));

        // **** close buffered reader ****
        br.close();

        // **** build linked list to be flattened ****
        LLNode head = build(strArr, arrs);

        // ???? ????
        System.out.println("main <<< head: " + llToString(head));

        // **** flatten linked list ****
        head = flatten(head);

        // ???? ????
        System.out.println("main <<< head: " + llToString(head));
    }

I am not going to spend too much time on the test code. The implementation follows the description of the test cases.

In a nutshell we created the initial linked list with the alternate linked lists using the build() method. The linked list is displayed.

We then flatten the linked list. The results are then displayed.

    /**
     * Build linked list to be flattened.
     * 
     * !!! NOT PART OF SOLUTION !!!
     */
    static LLNode build(String[] strArr, int[][] arrs) {

        // **** initialization ****
        LLNode head = null;
        LLNode tail = null;
        int altNum  = 0;

        // **** traverse String[] populating linked list to be flattened ****
        for (int i = 0; i < strArr.length; i++) {

            // **** primary node ****
            if (!strArr[i].equals("null")) {

                // **** create node ****
                LLNode node = new LLNode(Integer.parseInt(strArr[i]));

                // **** insert node into primary linked list ****
                if (head == null) {
                    head = node;
                    tail = node;
                } else {
                    tail.next = node;
                    tail = node;
                }
            } 
            
            // **** start of alternate linked list ****
            else {

                // **** create alternate node ****
                LLNode altNode = new LLNode(Integer.MAX_VALUE);

                // **** populate alternate linked list ****
                altNode.alt = populate(arrs[altNum++]);

                // **** add the alternate linked list to the linked list ****
                if (head == null) {
                    head = altNode;
                    tail = altNode;
                } else {
                    tail.next = altNode;
                    tail = altNode;
                }
            }
        }

        // **** return head of linked list ****
        return head;
    }

This method uses the data in the String[] array. When a null value is encountered, we attach to the alt node member the alternate linked list we generate with the values in the proper int[] array.

When done we return the primary linked list.

    /**
     * Populate alternate linked list
     * 
     * !!! NOT PART OF SOLUTION !!!
     */
    static LLNode populate(int[] arr) {

        // **** initialization ****
        LLNode head = null;
        LLNode tail = null;

        // **** populate alternate linked list ****
        for (int i = 0; i < arr.length; i++) {

            // **** ****
            LLNode node = new LLNode(arr[i]);

            // **** ****
            if (head == null) {
                head = node;
                tail = node;
            } else {
                tail.next = node;
                tail = node;
            }
        }

        // **** return head of alternate linked list ****
        return head;
    }

This method is used to generate an alternate linked list. The caller makes sure that the returned alternate linked list is pointed to by the alt member in the associated node.

    /**
     * Generate a string representation of a linked list.
     * 
     * !!! NOT PART OF SOLUTION !!!
     */
    static String llToString(LLNode head) {

        // **** initialization ****
        StringBuilder sb = new StringBuilder();

        // **** traverse the linked list ****
        for (LLNode p = head; p != null; p = p.next) {

            // **** ****
            if (p.val == Integer.MAX_VALUE)
                sb.append("X");
            else
                sb.append(p.toString());

            // **** separator ****
            if (p.next != null)
                sb.append("->");
        }

        // **** return the string representation ****
        return sb.toString();
    }

This is an auxiliary method. It is used to display linked lists.

    /**
     * Flatten linked list.
     * 
     * Runtime O(n);
     */
    static LLNode flatten(LLNode head) {

        // **** sanity check(s) ****
        if (head == null)
            return null;

        // **** initialization ****
        LLNode q = head;
        LLNode t;

        // **** traverse the linked list ****
        for (LLNode p = head; p != null; ) {

            // **** check if alternate linked list ****
            if (p.alt != null) {

                // **** save next node ****
                LLNode nextP = p.next;

                // **** append alternate to main linked list ****
                q.next = p.alt;

                // **** update head & q nodes (if needed) ****
                if (head == p) {
                    head    = p.alt;
                    q       = head;
                }

                // **** get to the tail of the alternate linked list ****
                for (t = p.alt; t.next != null; t = t.next);

                // **** tail.next point to next node in primary linked list ****
                t.next = nextP;

                // **** update pointers ****
                q = t;
                p = nextP;
            }

            // **** update pointers ****
            else {
                q = p;
                p = p.next;
            }
        }

        // **** return flattened linked list ****
        return head;
    }

The idea is to traverse the primary linked list until we encounter a special node; that is the one with the alternate linked list. Also note that the value of the special node is not part of the flattened linked list.

When we encounter one of the special nodes we store some information and point to the start of the alternate linked list so we can continue with its first node. We then traverse the alternate linked list until we get to the end of it. At that point we must proceed with the next element in the primary linked list. The special node will be garbage collected because we are no longer referring to it nor it is referring to a node in the primary linked list.

Note that as in any linked list, the first and last nodes might have to be dealt somewhat different. We have enough test cases to check most (never generalize) end conditions. Looking at the test cases, I can see that I missed two consecutive special nodes. If interested, please give that a try and let me know your findings.

If you think the test scaffolding is long and complex, I agree with you. I attempted to create the linked list passed to the method of interest in a way that would be close to how the problem is solved. I was considering a simpler way but will leave it as an exercise to the reader. The idea is to generate a long linked list (will be the result) and then randomly add special nodes and move a set of nodes to the alternate linked list. Repeat as needed. If you wish to experiment with such approach, let me know your findings and I will update this post to include the alternate test scaffold.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

One last thing, many thanks to all 6,526 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.

Regards;

John

john.canessa@gmail.com

2 thoughts on “Flatten a Linked List in Java”

  1. how to take multi line input as you in eclipse? It is terminating after clicking the main linked list and printing the output only for main

    1. Good day Karthik,

      Sorry I took so long to reply.

      I am not sure I follow what you are saying.
      Could you please rephrase the comment or send me a link to an article / reference that discusses the subject you brought up?

      I will reply shortly after receiving your update.

      Sincerely;

      John

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.