从给定的单链表中反转偶数（仅）

Question

我想反转 java 中单链表中的偶数，但我在获得正确输出时遇到了一些困难。例如，输入：2、18、24、3、5、7、9、6、12 该方法应该反转偶数 only 即 {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 class

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 class

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;

}

Answer 1

运行你的反向方法给了我一个与你看到的不同的输出。所以，我怀疑你的输出代码略有不同。

我得到：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;
}

Answer 2

我用的是python的列表，我只是想知道我是否可以不用链表来写这个程序。复杂度可能很高，但这只是一个有效的实验性实现

arr = [2,18,24,3,5,7,9,6,12]
arr_final = []
temp = []
for i in arr:
    if i%2 == 0:
        temp.append(i)
    else:
        if temp!=[]:
            temp.reverse()
            for j in temp:
                arr_final.append(j)
            temp = []
        arr_final.append(i)
if temp!=[]:
    temp.reverse()
    for j in temp:
        arr_final.append(j)
    temp = []

print(arr_final)

从给定的单链表中反转偶数（仅）

Reverse even numbers (Only) from given Singly Linked List

java

reverse

linked-list

singly-linked-list