java - 重新排列链接列表

Question

我正在尝试解决以下问题

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.

我真的不知道如何解决这个问题。我正在考虑的一种方法是识别具有负数据的节点并将其添加到头部，但我无法弄清楚如何编写这种方法。这是我的列表类。

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;
}
}

解决这个问题有什么提示/建议吗？

根据@nishu的建议，我提出了以下解决方案。它有效。

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

按照以下步骤进行进一步操作:

1. 创建方法:插入和删除。 insert - 它将在开头插入数据。 删除 - 它将搜索传递的值并删除列表中第一个出现的项目并返回被删除的节点。

2. 开始遍历链表。每当找到负节点时，将其从现有链表中删除，并在删除函数返回的节点上调用 insert 方法。