从给定的单链表中反转偶数(仅限)

hgb9j2n6  于 2021-07-08  发布在  Java
关注(0)|答案(1)|浏览(306)

我想在java中反转单链表中的偶数,但要获得正确的输出却面临一些困难。例如,input:2、18、24、3、5、7、9、6、12方法应该只反转偶数,即{2,18,24}和{6,12}
正确的输出:24、18、2、3、5、7、9、12、6
但是,我的输出:24 18 3 5 7 9 12 6哪个是错误的
主要方法

public static void main(String[] args) throws Exception {
    SLL<Integer> p = new SLL<Integer>();
    int[] e = { 2, 18, 24, 3, 5, 7, 9, 6, 12,5 ,4 ,3 ,2,6,8};

    for (int i = 0; i < e.length; i++) {
        p.addToHead(e[i]);

    }
    p = reverse(p);
    p.printAll();
}

这就是方法(不能正常工作)

public static SLL<Integer> reverse(SLL<Integer> p) {
    SLL<Integer> returnList = new SLL<Integer>();
    Stack<Integer> stk = new Stack<Integer>();

    for (SLLNode tmp = p.getHead(); tmp != null; tmp = tmp.next) {
        if ((((Integer) tmp.info) % 2) != 0) {
            returnList.addToHead((Integer) tmp.info);
            p.deleteFromHead();

        } else if ((((Integer) tmp.info) % 2) == 0) {
            stk.push((Integer) tmp.info);
            p.deleteFromHead();

        }
        if (stk.getLSize() >= 2) {

            while (!(stk.isEmpty())) {
                returnList.addToHead((Integer) stk.pop());
            }

        }
    }

    return returnList;
}

这是sllnode类

public class SLLNode<T> {

public T info;
public SLLNode<T> next;
public SLLNode() {
    this(null,null);
}
public SLLNode(T el) {
    this(el,null);
}
public SLLNode(T el, SLLNode<T> ptr) {
    info = el;
next = ptr;
}

}
这是sll类

public class SLL<T> {

protected SLLNode<T> head, tail;

public SLL() {
    head = tail = null;
}

public boolean isEmpty() {
    return head == null;
}

public void addToHead(T el) {
    head = new SLLNode<T>(el, head);
    if (tail == null)
        tail = head;
}
public SLLNode getHead(){
    return head;
}

public void addToTail(T el) {
    if (!isEmpty()) {
        tail.next = new SLLNode<T>(el);
        tail = tail.next;
    } else
        head = tail = new SLLNode<T>(el);
}

public T deleteFromHead() { // delete the head and return its info;
    if (isEmpty())
        return null;
    T el = head.info;
    if (head == tail) // if only one node on the list;
        head = tail = null;
    else
        head = head.next;
    return el;
}

public T deleteFromTail() { // delete the tail and return its info;
    if (isEmpty())
        return null;
    T el = tail.info;
    if (head == tail) // if only one node in the list;
        head = tail = null;
    else { // if more than one node in the list,
        SLLNode<T> tmp; // find the predecessor of tail;
        for (tmp = head; tmp.next != tail; tmp = tmp.next)
            ;
        tail = tmp; // the predecessor of tail becomes tail;
        tail.next = null;
    }
    return el;
}

public void delete(T el) { // delete the node with an element el;
    if (!isEmpty())
        if (head == tail && el.equals(head.info)) // if only one
            head = tail = null; // node on the list;
        else if (el.equals(head.info)) // if more than one node on the list;
            head = head.next; // and el is in the head node;
        else { // if more than one node in the list
            SLLNode<T> pred, tmp;// and el is in a nonhead node;
            for (pred = head, tmp = head.next; tmp != null
                    && !tmp.info.equals(el); pred = pred.next, tmp = tmp.next)
                ;
            if (tmp != null) { // if el was found;
                pred.next = tmp.next;
                if (tmp == tail) // if el is in the last node;
                    tail = pred;
            }
        }
}
public void printAll() {
    for (SLLNode<T> tmp = head; tmp != null; tmp = tmp.next)
        System.out.print(tmp.info + " ");
}

public boolean isInList(T el) {
    SLLNode<T> tmp;
    for (tmp = head; tmp != null && !tmp.info.equals(el); tmp = tmp.next)
        ;
    return tmp != null;
}

public int length() {
    int length = 0;
    for (SLLNode tmp = head; tmp != null; tmp = tmp.next) {

        length += 1;
    }
    return length;

}
qf9go6mv

qf9go6mv1#

运行你的反向方法给我一个与你看到的不同的输出。所以,我怀疑你的输出来自稍微不同的代码。
我得到:24,6,9,7,5,3,2,18
在反向方法中,当堆栈上有2个时,就开始向returnlist添加偶数。如果要反转所有偶数,则需要等待堆栈上的所有连续偶数。或者换句话说,当你得到一个奇数,或者没有剩下的数,你可以把所有的偶数从堆栈中弹出。。
我认为你也应该用addtail而不是addhead。
比如说

public static SLL<Integer> reverse(SLL<Integer> p) {
    SLL<Integer> returnList = new SLL<Integer>();
    Stack<Integer> stk = new Stack<Integer>();

    for (SLLNode tmp = p.getHead(); tmp != null; tmp = tmp.next) {
        if ((((Integer) tmp.info) % 2) != 0) {
            // add any stacked even numbers
            while (!(stk.isEmpty())) {
                returnList.addToTail((Integer) stk.pop());
            }
            // add the odd number
            returnList.addToTail((Integer) tmp.info);

        } else if ((((Integer) tmp.info) % 2) == 0) {
            System.out.println("even " + tmp.info);
            stk.push((Integer) tmp.info);

        }

    }
    // add any remaining even numbers from the stack
    while (!(stk.isEmpty())) {
        returnList.addToTail((Integer) stk.pop());
    }

    return returnList;
}

相关问题