java实现单链表反转

一、简介

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

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

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

二、实现

定义一个结点类：

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;

}