partition in a singly linked list

Question

I was doing this exercice:

Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x. Example input: 3 -> 5 -> 8 -> 5 -> 10 -> 2 -> 1 output: 3 -> 1 -> 2 -> 10 -> 5 -> 5 -> 8

I found it hard to find a solution for Singly linked list (that created by my own, not using library), I would like to know if there is uncessary code blocks in my code and is there a way to avoid putting in two lists and then merge? because it seems to have very slow performance like that.

    public CustomLinkedList partition(CustomLinkedList list, int x) {
    CustomLinkedList beforeL = new CustomLinkedList();
    CustomLinkedList afterL = new CustomLinkedList();
    LinkedListNode current = list.getHead();
    while (current != null) {
        if (current.getData() < x) {
            addToLinkedList(beforeL, current.getData());
        } else {
            addToLinkedList(afterL, current.getData());
        }
        // increment current
        current = current.getNext();
    }
    if (beforeL.getHead() == null)
        return afterL;
    mergeLinkedLists(beforeL, afterL);
    return beforeL;
}

public void addToLinkedList(CustomLinkedList list, int value) {
    LinkedListNode newEnd = new LinkedListNode(value);
    LinkedListNode cur = list.getHead();
    if (cur == null)
        list.setHead(newEnd);
    else {
        while (cur.getNext() != null) {
            cur = cur.getNext();
        }
        cur.setNext(newEnd);
        cur = newEnd;
    }
}

public void mergeLinkedLists(CustomLinkedList list1, CustomLinkedList list2) {
    LinkedListNode start = list1.getHead();
    LinkedListNode prev = null;
    while (start != null) {
        prev = start;
        start = start.getNext();        
    }
    prev.setNext(list2.getHead());
}

CustumLinkedList contains two attributes: -LinkedListNode which is the head and an int which is the size. LinkedListNode contains two attributes: One of type LinkedListNode pointing to next node and one of type int: data value

Thank you.

Answer 1

If you have any list of data, access orderByX Method. Hope it would help you.

public class OrderByX {
Nodes root = null;

OrderByX() {
    root = null;
}

void create(int[] array, int k) {
    for (int i = 0; i < array.length; ++i) {
        root = insert(root, array[i]);
    }
}

Nodes insert(Nodes root, int data) {
    if (root == null) {
        root = new Nodes(data);
    } else {
        Nodes tempNew = new Nodes(data);
        tempNew.setNext(root);
        root = tempNew;
    }
    return root;
}

void display() {
    Nodes tempNode = root;
    while (tempNode != null) {
        System.out.print(tempNode.getData() + ",  ");
        tempNode = tempNode.getNext();
    }
}

void displayOrder(Nodes root) {
    if (root == null) {
        return;
    } else {
        displayOrder(root.getNext());
        System.out.print(root.getData() + ",  ");
    }

}

Nodes orderByX(Nodes root, int x) {
    Nodes resultNode = null;
    Nodes lessNode = null;
    Nodes greatNode = null;
    Nodes midNode = null;
    while (root != null) {
        if (root.getData() < x) {
            if (lessNode == null) {
                lessNode = root;
                root = root.getNext();
                lessNode.setNext(null);
            } else {
                Nodes temp = root.getNext();
                root.setNext(lessNode);
                lessNode = root;
                root = temp;
            }
        } else if (root.getData() > x) {
            if (greatNode == null) {
                greatNode = root;
                root = root.getNext();
                greatNode.setNext(null);
            } else {
                Nodes temp = root.getNext();
                root.setNext(greatNode);
                greatNode = root;
                root = temp;
            }
        } else {

            if (midNode == null) {
                midNode = root;
                root = root.getNext();
                midNode.setNext(null);
            } else {
                Nodes temp = root.getNext();
                root.setNext(midNode);
                midNode = root;
                root = temp;
            }

        }
    }
    resultNode = lessNode;
    while (lessNode.getNext() != null) {
        lessNode = lessNode.getNext();
    }
    lessNode.setNext(midNode);
    while (midNode.getNext() != null) {
        midNode = midNode.getNext();
    }
    midNode.setNext(greatNode);
    return resultNode;
}

public static void main(String... args) {
    int[] array = { 7, 1, 6, 2, 8 };
    OrderByX obj = new OrderByX();
    obj.create(array, 0);
    obj.display();
    System.out.println();
    obj.displayOrder(obj.root);
    System.out.println();
    obj.root = obj.orderByX(obj.root, 2);
    obj.display();

}
}

class Nodes {

private int data;
private Nodes next;

Nodes(int data) {
    this.data = data;
    this.next = null;
}

public Nodes getNext() {
    return next;
}

public void setNext(Nodes next) {
    this.next = next;
}

public int getData() {
    return data;
}

public void setData(int data) {
    this.data = data;
}

}

Answer 2

The problem of your code is not merging two lists as you mentioned. It's wrong to use the word merge here because you're only linking up the tail of the left list with head of right list which is a constant time operation.

The real problem is - on inserting a new element on the left or right list, you are iterating from head to tail every time which yields in-total O(n^2) operation and is definitely slow.

Here I've wrote a simpler version and avoid iterating every time from head to insert a new item by keeping track of the current tail.

The code is very simple and is definitely faster than yours(O(n)). Let me know if you need explanation on any part.

// I don't know how your CustomLinkedList is implemented. Here I wrote a simple LinkedList node
public class ListNode {
    private int val;
    private ListNode next;
    public ListNode(int x) {
        val = x;
    }
    public int getValue() {
        return this.val;
    }
    public ListNode getNext() {
        return this.next;
    }
    public void setNext(ListNode next) {
        this.next = next;
    }
}

public ListNode partition(ListNode head, int x) {

    if(head == null) return null;

    ListNode left = null;
    ListNode right = null;

    ListNode iterL = left;
    ListNode iterR = right;

    while(iter != null) {

        if(iter.getValue() < x) {
            iterL = addNode(iterL, iter.getValue());
         }
        else {
            iterR = addNode(iterR, iter.getValue());
        }

        iter = iter.getNext();
    }

    // link up the left and right list
    iterL.setNext(iterR);

    return left;
}

public ListNode addNode(ListNode curr, int value) {

    ListNode* newNode = new ListNode(value);

    if(curr == null) {
        curr = newNode;
    } else {
       curr.setNext(newNode);
       curr = curr.getNext();
    }

    return curr;
}

Hope it helps!

Answer 3

I think that maintaining two lists is not an issue. It is possible to use a single list, but at the cost of loosing some of the simplicity.

The principal problem seems to be the addToLinkedList(CustomLinkedList list, int value) method.

It iterates throughout the entire list in order to add a new element.

One alternative is to always add elements at the front of the list. This would also produce a valid solution, and would run faster.