CODEWITHSUNDEEP
javadata-structureslinked-listnodes
CeilingSystems
CeilingSystems

Reputation: 187

Recursively split a LinkedList in Java into odd and even lists

I am trying to solve a problem where I am given a LinkedList with data integers and am tasked with splitting the List into two separate lists, one with all even positions and one with all odd.

Input: 0 1 2 3 0 -4 -5

ListNode class:

public class ListNode
{
    public int data;
    public ListNode next;

    public ListNode(int _data)
    {
        data = _data;
        next = null;
    }
}

Driver method:

    public static void main(String [] args) {
        MyList L = new MyList();
        ListNode head = L.getHead();        // Get the head node of the linked list.
        System.out.print("INPUT: ");
        print(head);
        ListNode [] R = split(head);        // Split into two list. The first list contains all elements in odd positions, the second contains all elements at even positions.
        System.out.println("Printing the list with odd positions");
        print(R[0]);
        System.out.println("Printing the list with even positions");
        print(R[1]);
    }

I am struggling of thinking of a way to do this, I am not given any helper methods to add a node, here is something that I have tried but does not work properly.

private static ListNode[] split(ListNode L)
    {
        ListNode[] ret = new ListNode[2];
        
        for (ListNode cur = L; cur != null; cur = cur.next)
        {
            if ((cur.data % 2) == 0)
            {
                ret[1] = cur;
                ret[1].data = cur.data;
                System.out.print("CURRENT EVEN LIST IS ");
                print(ret[1]);
            }
            else
            {
                ret[0] = cur;
                ret[0].data = cur.data;
                System.out.print("CURRENT ODD LIST IS ");
                print(ret[0]);
            }
        }
        return ret;
    }

and here is the output that I get:

INPUT: 0 1 2 3 0 -4 -5 
CURRENT EVEN LIST IS 0 1 2 3 0 -4 -5 
CURRENT ODD LIST IS 1 2 3 0 -4 -5 
CURRENT EVEN LIST IS 2 3 0 -4 -5 
CURRENT ODD LIST IS 3 0 -4 -5 
CURRENT EVEN LIST IS 0 -4 -5 
CURRENT EVEN LIST IS -4 -5 
CURRENT ODD LIST IS -5 
Printing the list with odd positions
-5 
Printing the list with even positions
-4 -5

I am hoping that someone can lead me on the right track, I know that my attempt is wrong because it always copies the whole list, but I know that I am missing something. Is there a recursive approach to this?

Thank you

Upvotes: 0

Views: 618

Answers (2)

Shaan K
Shaan K

Reputation: 376

In a singly linked list, the head node implicitly represents the entire list and the second node represents itself and the remainder of the list.

When you do this ret[1] = cur; when cur is the head node you are just setting that index to be the entire list and in the next iteration of the for loop when cur is the second node ret[1] = cur; will set ret[1] to the entire list minus the previous node.

You need to alter connections in the original list. Try drawing it out.

The original list had connections like this:

(0) -> (1) -> (2) -> (3) -> (0) -> (-4) -> (-5)

You want this:

(0) -> (2) -> (0) -> (-5)

(1) -> (3) -> (-4)

Setting connections/links will be done with next field in the node definition. You will have to break connections, and set new ones.

For example, the next field of the first (0) will be the original next field of (1) with code like this: cur.next = cur.next.next;

Upvotes: 1

karakfa
karakfa

Reputation: 67467

Here is one recursive implementation.

    private void split(Predicate<Integer> p, ListNode n, Pair<ListNode> pair) {
        if (null == n) {
            return;
        }

        if (p.test(n.data)) {
            pair.left = pair.left.next = n;
        } else {
            pair.right = pair.right.next = n;
        }

        ListNode nn = n.next;
        n.next = null;
        split(p, nn, pair);
    }

recursive run needs to carry the split lists as well. I used a Pair instead of an array, which is just

static class Pair<T> {
    T left, right;

    public Pair(T left, T right) {
        this.left = left;
        this.right = right;
    }
}

to start the recursive split, you need to create the Pair with dummy root objects so that you can eliminate null checks in the recursive step for the first entries. Once done, just peel the headers and return the rest

    Pair<ListNode> split(Predicate<Integer> p) {
        ListNode leftRoot = new ListNode(0);
        ListNode rightRoot = new ListNode(0);
        Pair<ListNode> pair = new Pair<>(leftRoot, rightRoot);
        split(p, this, pair);
        return new Pair<>(leftRoot.next, rightRoot.next);
    }

just call the entry split with the right predicate

    int[] input = {0, 1, 2, 3, 0, -4, -5};
    ListNode ln = ... // initialize for the input

    Predicate<Integer> even = i -> i % 2 == 0;
    Pair<ListNode> split = ln.split(even);
    System.out.println(split.left);
    System.out.println(split.right);

if you write a toString() method to get the contents in a nice format

for example, with this

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(data).append(" -> ");
        ListNode n = this;
        while (null != (n = n.next)) {
            sb.append(n.data).append(" -> ");
        }
        return sb.toString();
    }

you'll get the output:

0 -> 2 -> 0 -> -4 -> 
1 -> 3 -> -5 ->

Upvotes: 1

Related Questions