单链表原地反序

「原地」指的是除给出类之外,不借助其他的辅助结构

/** 带头指针的单链表原地逆序(逆序函数为reverse)
* Created by Willow on 1/5/17.
*/
public class List {
  Node head;
  public List(Node head) {
    this.head = head;
  }
  //节点
  static class Node {
    int data;
    Node next;
    public Node() {}
    public Node(int data, Node next) {
      this.data = data;
      this.next = next;
    }
  }
  //逆序
  public void reverse() {
    if (null == head || null == head.next || null == head.next.next)
      return;
    Node pre = null, cur = this.head.next, nex = cur.next;
    while (null != nex) {
      //1. 逆置当前节点指向
      cur.next = pre;
      //2. 前置、当前、后置节点的三个指针向前移动
      pre = cur;
      cur = nex;
      nex = nex.next;
    }
    cur.next = pre;//3. 逆置最后一个节点的指向
    this.head.next = cur;//4. 头指针指向最后一个节点
  }
  //遍历
  public void traverse() {
    if (null == head.next)
      return;
    Node cur = head.next;
    while (null != cur) {
      System.out.println(cur.data);
      cur = cur.next;
    }
    System.out.println("traverse end \n");
  }
  //测试入口
  public static void main(String[] args) {
    Node n7 = new Node(7, null);
    Node n6 = new Node(6, n7);
    Node n5 = new Node(5, n6);
    Node n4 = new Node(4, n5);
    Node n3 = new Node(3, n4);
    Node n2 = new Node(2, n3);
    Node n1 = new Node(1, n2);
    Node head = new Node(0, n1);
    List list = new List(head);
    list.traverse();
    list.reverse();
    list.traverse();
  }
}