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进行对比，循环的时间和空间都比迭代更好。

为什么迭代更常用呢？