Java实现单链表翻转实例代码

/**

 * 反转单链表

 */

/** * 定义链表

 *

 * @author 16026

 *

 */

classNode {

  intval;

  Node next;

  publicNode(intval) {

    this.val = val;

  }

}

publicclassReverseList {

  /**

   * 反转链表

   *

   * @param head

   * @return

   */

  publicstaticNode reverseList(Node head) {

    if(head ==null|| head.next ==null) {

      returnhead;

    }

    Node reHead =null;// 定义新链表头结点

    while(head !=null) {

      Node cur = head.next;// 记录下一个节点

      head.next = reHead;// 将rehead节点连接到head节点上

      reHead = head;// 让rehead指向head

      head = cur;// 将head指向下一个节点

    }

    returnreHead;

  }

  /**

   * 递归反转链表

   *

   * @param head

   * @return

   */

  publicstaticNode reverseList2(Node head) {

    if(head ==null|| head.next ==null)

      returnhead;

    Node rehead = reverseList2(head.next);

    head.next.next = head;// 将头节点置于末端

    head.next =null;// 防止链表循环

    returnrehead;

  }

  /**

   * 打印链表

   *

   * @param head

   */

  publicstaticvoidprintList(Node head) {

    if(head ==null)

      return;

    while(head !=null) {

      System.out.print(head.val +" ");

      head = head.next;

    }

  }

  /**

   * 测试

   *

   * @param args

   */

  publicstaticvoidmain(String[] args) {

    Node n1 =newNode(1);

    Node n2 =newNode(2);

    Node n3 =newNode(3);

    Node n4 =newNode(4);

    Node n5 =newNode(5);

    n1.next = n2;

    n2.next = n3;

    n3.next = n4;

    n4.next = n5;

    // Node rehead = reverseList(n1);

    Node rehead = reverseList2(n1);

    printList(rehead);

  }

}