欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2024-03-03 14:43:34
java实现单链表反转,递归和非递归两种形式 /** * 反转单链表 */ /** * 定义链表 * * @author 16026...

java实现单链表反转,递归和非递归两种形式

/**
 * 反转单链表
 */

/** * 定义链表
 * 
 * @author 16026
 *
 */
class node {
  int val;
  node next;
  public node(int val) {
    this.val = val;
  }
}
public class reverselist {
  /**
   * 反转链表
   * 
   * @param head
   * @return
   */
  public static node reverselist(node head) {
    if (head == null || head.next == null) {
      return head;
    }
    node rehead = null;// 定义新链表头结点
    while (head != null) {
      node cur = head.next;// 记录下一个节点
      head.next = rehead;// 将rehead节点连接到head节点上
      rehead = head;// 让rehead指向head
      head = cur;// 将head指向下一个节点
    }
    return rehead;
  }
  /**
   * 递归反转链表
   * 
   * @param head
   * @return
   */
  public static node reverselist2(node head) {
    if (head == null || head.next == null)
      return head;
    node rehead = reverselist2(head.next);
    head.next.next = head;// 将头节点置于末端
    head.next = null;// 防止链表循环
    return rehead;
  }
  /**
   * 打印链表
   * 
   * @param head
   */
  public static void printlist(node head) {
    if (head == null)
      return;
    while (head != null) {
      system.out.print(head.val + " ");
      head = head.next;
    }
  }
  /**
   * 测试
   * 
   * @param args
   */
  public static void main(string[] args) {
    node n1 = new node(1);
    node n2 = new node(2);
    node n3 = new node(3);
    node n4 = new node(4);
    node n5 = new node(5);
    n1.next = n2;
    n2.next = n3;
    n3.next = n4;
    n4.next = n5;
    // node rehead = reverselist(n1);
    node rehead = reverselist2(n1);
    printlist(rehead);
  }
}

运行结果如下:

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

以上所述是小编给大家介绍的java实现单链表翻转实例代码,希望对大家有所帮助