Rearranging a linked list

Question

I'm trying to solve the following problem

Write a method split that rearranges the elements of a list so that all of the negative values appear before all of the non-negatives. For example, suppose a variable list stores the following sequence of values:

[8, 7, -4, 19, 0, 43, -8, -7, 2]

The call of list.split(); should rearrange the list to put the negatives first. One possible arrangement would be the following:

[-4, -8, -7, 8, 7, 19, 0, 43, 2]

But it matters only that the negatives appear before the non-negatives. So this is only one possible solution. Another legal solution would be to rearrange the values this way:

[-7, -8, -4, 2, 43, 0, 19, 7, 8]

You are not allowed to swap data fields or to create any new nodes to solve this problem; you must rearrange the list by rearranging the links of the list. You also may not use auxiliary structures like arrays, ArrayLists, stacks, queues, etc, to solve this problem.

I'm really clueless as how to solve this problem. One approach which I'm thinking of is to identify nodes with negative data and add it to the head, but I'm unable to figure out how to code this approach. Here is my list class.

public class LinkedList {

// The Linked List's Node structure
   static class Node {
    private Node next;
    private int data;

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

    public int getData() {
        return data;
    }

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

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

    public Node getNext() {
        return next;
    }

}

private Node head;
private int size;

public void setHead(Node head) {
    this.head = head;
}

public int getSize() {
    return size;
}

public Node getHead() {
    return head;
}

public LinkedList() {
    head = null;
    size = 0;
}
}

Any hints/suggestion for tackling this problem?

As suggested by @nishu I have come up with the following solution. It works.

public Node delete(int data) {

    Node del = null;
    Node tmp = head;
    if (head.getData() == data) {
        Node tmp2 = head;
        Node nxt = tmp.getNext();
        tmp2.setNext(null);
        this.setHead(nxt);
        del = tmp2;
    } else if (isLast(data)) {
        while (true) {
            if (tmp.getNext().getNext() == null) {
                del = tmp.getNext();
                tmp.setNext(null);
                break;
            }
            tmp = tmp.getNext();
        }
    } else {
        while (tmp != null && tmp.getNext() != null) {
            if (tmp.getNext().getData() == data) {
                Node prev = tmp;
                del = tmp.getNext();
                Node nextOfToBeDeleted = tmp.getNext().getNext();
                prev.setNext(nextOfToBeDeleted);
                break;
            }
            tmp = tmp.getNext();
        }
    }
    return del;
}

public void addToFront(Node node) {
    node.setNext(head);
    this.setHead(node);
}

public void split() {

    Node tmp = head;
    Node del = null;
    while (tmp != null) {
        if (tmp.getData() < 0) {
            Node nxt = tmp.getNext();
            del = delete(tmp.getData());
            addToFront(del);
            while (tmp != nxt) {
                tmp = tmp.getNext();
            }
        } else {
            tmp = tmp.getNext();
        }

    }
}

public boolean isLast(int data) {
    boolean last = false;
    Node tmp = head;
    while (true) {
        if (tmp.getData() == data && tmp.getNext() != null) {
            last = false;
            break;
        } else if (tmp.getNext() == null && tmp.getData() == data) {
            last = true;
            break;
        }
        tmp = tmp.getNext();
    }
    return last;
}

Answer 1

Follow the procedure to go further :

1. create methods : insert and delete. insert - it will insert data at the beginning. delete - it will search for the value passed and delete the first occurrence of item in the list and returns the node that was deleted.

2. Start traversing the linked list. Whenever you find a negative node, delete it from existing linked list and call insert method on the node returned by delete function.