链表一种在物理存储单元上非连续、非顺序的一种存储结构，元素通过链表中的指针链接次序实现。链表是由节点组成，每一个节点包括两部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。相比于线性表，操作变得复杂，但是对于数据的删除和增加要快。
链表结构图.png
Java代码实现链表
public class MyList {
private Node head; // 定义一个头节点
private Node current; // 记录当前节点
public static void main(String[] args) {
MyList myList = new MyList();
for (int i = 0; i < 5; i++) {
myList.addData(i); // 循环添加5个元素
}
myList.printList(myList.head); //打印链表
}
// 往链表中添加数据
private void addData(int data) {
if (head == null) {
head = new Node(data); // 如果头节点为空，就新建一个头结点
current = head; // 记录当前节点为头结点
} else {
current.next = new Node(data); // 新建一个节点，当前节点的指针域指向它
current = current.next; // 当前节点位置后移
}
}
// 打印链表
private void printList(Node head) {
if (head != null) { // 确定链表不为空
current = head;
while (current!= null) { // 最后一个节点的为空
System.out.print(current.data + "-->");
current = current.next; // 当前节点往后移动一个位置
}
}
}
// 自定义节点类，包含数据域和指针域
class Node {
int data; // 数据域
Node next; // 指针域
public Node(int data) {
this.data = data;
}
}
}
链表倒置问题
一些公司经常拿来做为笔试题，至少在我刚出来实习时前几次面试中就碰到过两次。所以还是有必要进行细心准备一下。以下在上面实现的链表基础上进行倒置。
- 递归倒置法
在反转当前节点之前先反转后续节点。这样从头结点开始，层层深入直到尾结点才开始反转指针域的指向。简单的说就是从尾结点开始，逆向反转各个结点的指针域指向
// 递归倒置链表
private Node resetList1(Node head) {
if (head == null || head.next == null) {
return head; // 若为空链或者当前结点在尾结点，则直接返回
} else {
Node newHead = resetList1(head.next); //反转后续节点head.next
head.next.next = head; //将当前节点的指针域向前移
head.next = null; //前一节点的指针域置空
return newHead;
}
}
- 遍历反转法
从前往后，通过生成一个临时节点next进行下一节点缓存，指针反转后，再将缓存节点赋值给当前节点，这样往后移动
// 遍历方法倒置
private Node resetList2(Node head) {
Node current = head;
Node next = null;
Node newHead = null;
if (head == null || head.next == null) {
return head;
} else {
while (current != null) { //为空时到了尾节点
next = current.next; //新结点next缓存下一个节点
current.next = newHead; //指针域反转
newHead = current; //将当前节点给newHead
current = next; //移动到下一个节点
}
}
return newHead;
}
