//单链表反序

public class SingleLinkedListReverse {

	public static void main(String[] args) {

		Node head = new Node(0);

		Node temp = null;

		Node cur = null;

		for (int i = 1; i <= 10; i++) {

			temp = new Node(i);

			if (i == 1) {

				head.setNext(temp);

			} else {

				cur.setNext(temp);

			}

			cur = temp;

		}//10.next = null;

		Node h = head;

		while (h != null) {

			System.out.print(h.getData() + "\t");

			h = h.getNext();

		}

		System.out.println();

		//反转1

//		h = Node.reverse1(head);

//		while (h != null) {

//			System.out.print(h.getData() + "\t");

//			h = h.getNext();

//		}

		//反转2

		h = Node.reverse1(head);

		while (h != null) {

			System.out.print(h.getData() + "\t");

			h = h.getNext();

		}

	}

}

/*

 * 单链表的每一个节点都含有指向下一个节点属性

 */

class Node {

	Object data;//数据对象

	Node next; //下一节点

	Node(Object d) {

		this.data = d;

	}

	Node(Object d, Node n) {

		this.data = d;

		this.next = n;

	}

	public Object getData() {

		return data;

	}

	public void setData(Object data) {

		this.data = data;

	}

	public Node getNext() {

		return next;

	}

	public void setNext(Node next) {

		this.next = next;

	}

	//方法1  head被重置

	static Node reverse1(Node head) {

		Node p = null; //反转后新的 头

		Node q = head;

		//轮换结果：012,123,234,.... 10 null null

		while (head.next != null) {

			p = head.next;		// 第1个 换成第2个  这时p表示原始序列头中的next

			head.next = p.next;  // 第2个 换成第3个

			p.next = q;			//已经跑到第1位置的原第2个的下一个 就要变成 原第1个

			q = p;				//新的第1个 要变成 当前第一个

		}

		return p;

	}

	//方法2 head没重置

	static Node reverse2(Node head) {

		//将中间节点的指针指向前一个节点之后仍然能够继续向后遍历链表

		Node p1 = head, p2 = head.next, p3; // 前 中 后

		//轮换结果 ：012, 123, 234, 345, 456.... 9 10 null

		while (p2 != null) {

			p3 = p2.next;

			p2.next = p1; //指向后 变 指向前

			p1 = p2; 	 //2、3向前挪

			p2 = p3;

		}

		head.next = null;//head没变，当输出到0时。再请求0.next 为1

		return p1;

	}

}