Java单向链表反转

Java API中的链表是双向的，我们这里自己新建一个类代表我们的链表元素结点：

class Node {		int value;		Node next;		public Node(int i) {			setValue(i);		}		public Node() {		}		public int getValue() {			return value;		}		public void setValue(int value) {			this.value = value;		}		public Node getNext() {			return next;		}		public void setNext(Node next) {			this.next = next;		}	}

 然后我们拼接一根链表：

Node linkedList = new Node();		linkedList.setValue(1);		Node current = linkedList;		for (int i = 2; i < 10; i++) {			Node tNode = new Node(i);			current.setNext(tNode);			current = tNode;		}

 这跟链表有9个元素，从1一直指向9.

第一种方法需要两个额外的结点空间，通过循环不停的反向相邻结点并记录后续的位置：

	private Node reverse(Node head) {		Node temp = head.getNext();		Node flag = temp.getNext();		head.setNext(null);		while (flag != null) {			temp.setNext(head);			head = temp;			temp = flag;			flag = flag.getNext();		}		temp.next = head;		return temp;	}

 把链表头结点传入即可实现反转并返回新的头结点。

我努力尝试了使用一个额外结点实现反转，没能成功：

	private Node reverse(Node head) {		Node temp = head.getNext();		while (temp.getNext() != null) {			head.getNext().setNext(head);			head = temp;			temp = temp.next;		}		temp.next = head;		return temp;	}

 如果各位有只使用一个额外空间就能反转的请留言指点，谢谢。

第二种反转方法是使用迭代，需要传入链表的前两个元素：

	private Node reverseRecur(Node head, Node next) {		if (next == null) {			return head;		}		if (head.getNext().equals(next)) {//第一次进来			head.setNext(null);		}		if (next.getNext() != null) {			Node next2 = next.getNext();			next.setNext(head);			return reverseRecur2(next, next2);		}		next.setNext(head);		return next;	}

 我努力尝试只传入头结点来反转，但是总是不成功：

	private Node reverseRecur(Node head) {		Node tail = head.getNext();		if (tail.getNext() != null) {			Node flag = reverseRecur(tail);			flag.setNext(head);			head.setNext(null);			return head;		}		tail.setNext(head);		head.setNext(null);		return head;	}

我将链表长度设置为10000进行对比，循环的时间和空间都比迭代更好。

为什么迭代更常用呢？