java实现单链表反转

时间:2021-07-12 08:50:25

一、简介

  经查阅,主要有两种方法实现链表反转,递归反转法和遍历反转法;

  递归: 在反转当前结点之前先反转其后边的结点,即、从尾结点开始逆向反转各个节点的指针域指向;

  遍历:从前往后反转各个结点的指针域的指向。

二、实现

定义一个结点类:

public class Node {

private int data;  //数据域
 private Node next;    //指针域
  
 
 public Node(int data) {
  super();
  this.data = data;
 }
 public int getData() {
  return data;
 }
 public void setData(int data) {
  this.data = data;
 }
 public Node getNext() {
  return next;
 }
 public void setNext(Node next) {
  this.next = next;
 }
 
}

递归反转:

public static Node reverse(Node head){

//如果是空链表或者尾结点
  if (head==null||head.getNext()==null) {
   return head;
  }

//先反转后续结点
  Node reversedHead=reverse(head.getNext());

//当前结点指针指向前一结点
  head.getNext().setNext(head);

//令前一结点的指针域为null
  head.setNext(null);
  return reversedHead;
 }

遍历反转:

public static Node reverse1(Node head){
  
  if (head==null) {
   return head;
  }

//上一结点
  Node pre=head;

//当前结点
  Node cur=head.getNext();

//用于存储下一节点
  Node tem;

//cur==null 即尾结点
  while(cur!=null){

//下一节点存入临时结点
   tem=cur.getNext();

//将当前结点指针指向上一节点
   cur.setNext(pre);

//移动指针
   pre=cur;
   cur=tem;
  }
  head.setNext(null);
  return pre;
 }