结点类：
/**
* @author zhengbinMac
* 一个OnelinkNode类的对象只表示链表中的一个结点，通过成员变量next的自引用方式实现线性表中各数据元素的逻辑关系。
*/
public class OnelinkNode {
// 保存结点的值
public int data;
// 保存后继结点的引用
public OnelinkNode next;
// 构造值为k的结点
public OnelinkNode(int k) {
data = k;
next = null;
}
// 初始化单向链表
public OnelinkNode() {
this(0);
}
}
单向链表类：
/**
* @author zhengbinMac
* Onelink1类的一个对象表示一条单向链表，成员变量head作为链表的头指针，指向
* 链表的第一个结点。head为被保护的（protected），可被其子类继承。
* 当head为null时，表示链表为空，元素个数为0。
*/
public class Onelink1 {
// 指向链表的第一个结点
protected OnelinkNode head;
// 创建一个空的单向链表
public Onelink1() {
head = null;
}
// 构造由h1指向的单向链表
public Onelink1(OnelinkNode h1) {
head = h1;
}
/**
* 判断链表是否为空
*/
public boolean isEmpty() {
return head == null;
}
/**
* 以n个随机值建立单向链表
*/
public Onelink1(int n) {
OnelinkNode rear,q;
if(n > 0) {
int k = (int)(Math.random() * 100);//产生随机数，加入链表
head = new OnelinkNode(k);
rear = head;
for(int i = 1;i < n;i++) {
k = (int)(Math.random() * 100);
q = new OnelinkNode(k);
rear.next = q;
rear = q;
}
}
}
/**
* 返回链表的长度
*/
public int length() {
int n = 0;
OnelinkNode p = head;
while(p != null) {
n++;
p = p.next;
}
return n;
}
/**
* 输出链表
*/
public void output() {
this.output(head);
}
private void output(OnelinkNode head) {
System.out.print(this.getClass().getName() + ": ");
while(head != null) {
System.out.print(head.data);
head = head.next;
if(head != null) {
System.out.print(" -> ");
}
}
System.out.println();
}
}
单向链表的反转：
/**
* @author zhengbinMac
*/
public class Onelink2 extends Onelink1{
public Onelink2() {
super();
}
public Onelink2(int n) {
super(n);
}
public void reverse() {
OnelinkNode p = this.head, q = null, front = null;
/*
* 以下面这个链表为例：
* 1->2->3->4
*/
while(p != null) {
q = p.next; // p = 1, q = 2;
p.next = front; // 1.next = null;下次循环将变为：2.next = 1;
front = p; // front = 1;
p = q; // p = 2;
}
this.head = front;// 循环结束后，front指向原链表的最后一个结点，
}
public static void main(String[] args) {
Onelink2 h2 = new Onelink2(5);
h2.output();
System.out.println("Reverse!");
h2.reverse();
h2.output();
}
}
在线编程：
牛客网——《剑指Offer》-反转链表