I have read this stackoverflow thread
I want to test if it works.
However, the result was not expected, it should print out
apple
orange
banana
instead of
apple
banana
My testing code
import java.util.Iterator;
public class LinkedList<Item> implements Iterable<Item> {
private Node first;
private Node last;
private int N = 0;
private class Node {
Item item;
Node next;
}
public LinkedList() {
first = last = null;
}
public int size() { return N; }
public void insertAtBegin(Item item2insert) {
if (first == null) {
Node node = new Node();
node.item = item2insert;
node.next = null;
last = first = node;
N = N + 1;
} else {
Node new_first = new Node();
new_first.item = item2insert;
new_first.next = first;
first = new_first;
N = N + 1;
}
}
public Item removeFromBegin() {
if (N == 0) {
throw new java.util.NoSuchElementException("Removing from a null list");
}
Item item2return = first.item;
if (first == last) {
first = last = null;
} else {
first = first.next;
}
N = N - 1;
return item2return;
}
public void insertAtEnd(Item item) {
if (first == null) {
Node node = new Node();
node.item = item;
node.next = null;
first = last = node;
} else {
Node new_last = new Node();
new_last.item = item;
new_last.next = null;
last.next = new_last;
last = new_last;
}
N = N + 1;
}
public Node reverse(Node node_first) {
if (node_first == null) { return null; }
if (node_first.next == null) { return node_first; }
Node second = node_first.next;
first.next = null;
Node rest = reverse(second);
second.next = first;
return rest;
}
public void reverseList() {
first = reverse(first);
}
public Iterator<Item> iterator() { return new LinkedListIterator(); }
private class LinkedListIterator implements Iterator<Item> {
private Node current = first;
public boolean hasNext() { return current != null; }
public void remove() { throw new java.lang.UnsupportedOperationException("Unsupported remove!"); }
public Item next() {
Item item = current.item;
current = current.next;
return item;
}
}
public static void main(String[] args) {
LinkedList<String> s = new LinkedList<String>();
s.insertAtBegin("apple");
s.insertAtBegin("orange");
s.insertAtBegin("banana");
for (String fruit : s)
StdOut.println(fruit);
StdOut.println("\n==========================\n");
s.reverseList();
for (String fruit : s)
StdOut.println(fruit);
}
}
update: the iteration version works
public Node recurReverse(Node x) {
Node reverse = null;
while (x != null) {
Node second = x.next;
x.next = reverse;
reverse = x;
x = second;
}
return reverse;
}
public void reverseList() {
first = recurReverse(first);
}