将1->2->3->4->5->6->7 变成 1->7->2->6->3->5->4，recursive解法

ReverseInsert.java

package mine.coding;

public class ReverseInsert {

	private static class Node {
		public int val;
		public Node next;

		public Node(int val) {
			this.val = val;
			this.next = null;
		}
	}

	Node start;

	/**
	 * 将1->2->3->4->5->6->7 变成 1->7->2->6->3->5->4，recursive解法
	 */
	private void rev(Node end) {
		if (end.next != null)
			rev(end.next); // find the last node
		
		// visit all 'last nodes'
		if(start!=null){// already over
			if (start == end || start.next == end) { // first over
				end.next = null; // end the chain
				start=null; // mark as over
			} else {
				// insert node
				end.next = start.next;
				start.next = end;
				start = end.next;
			}	
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Node root = new Node(1);
		Node cur = root;
		for (int i = 2; i <= 7; i++) {
			cur.next = new Node(i);
			cur = cur.next;
		}
		ReverseInsert sol = new ReverseInsert();
		sol.start = root;
		if (root != null && root.next != null)
			sol.rev(root.next);

		while (root != null) {
			System.out.print(root.val + "\t-->\t");
			root = root.next;
		}
	}

}