目录
前言
自定义“单向”链表类
1. 自定义一个链表类，并完成“初始化链表”、“添加元素（头插法/尾插法）”、“计算链表长度”操作；
自定义链表
向链表中插入元素（头插法）
向链表中插入元素（尾插法）
计算链表长度
重写toString()方法
测试类
测试结果
对链表的应用
2. 在自定义链表类的基础上，使用“双指针”实现两个链表的合并；
测试用例
测试结果
测试用例
测试结果
4. 在自定义链表类的基础上，计算两个大型整数(BigInteger)和；
测试用例
测试结果
5.1 在自定义链表类的基础上，使用"Set"集合 测试链表中是否存在环路现象；
测试用例
测试结果
5.2 在自定义链表类的基础上，基于"快慢指针"判断链表中是否存在环路；
测试用例
测试结果
前言
链表的特点：
链表的优点：
- 不需要提前预估长度，较于“数组”不存在“扩容操作”；
- 使用不连续的内存空间，实现灵活的内存动态管理；
链表的缺点：
- 较于数组会占用更多空间，因为其需要存放其他节点的指针；
- 不支持随机读取元素(RandomAccess) —— 数组类实现类一个标准类 RandomAccess表示支持随机读取；
- 遍历和查找元素较慢，适合读少写多的操作；
链表的时间复杂度：
- 插入和删除操作的复杂度为 O(1)；
- 查找或访问某一特定节点复杂度为 O(n)；
链表的分类：
自定义“单向”链表类
1. 自定义一个链表类，并完成“初始化链表”、“添加元素（头插法/尾插法）”、“计算链表长度”操作；
-
自定义链表
java">public class Linked{
//定义头节点和尾节点
private Node first,last;
//链表长度
private int size;
//定义链表的节点
static class Node{
int val; //数据域
Node next; //后继元素(下一个元素)
public Node(int x){
this.val =x;
}
}
}解读：
-
向链表中插入元素（头插法）
java">public class Linked{
// 添加元素(头插法)
public void addFirst(int val) {
// 创建新节点
final Node newNode = new Node(val);
// 将新节点的 next 指向当前的第一个节点
newNode.next = first;
// 更新头节点为新节点
first = newNode;
// 如果链表为空，则更新尾节点为新节点
if (last == null) {
last = newNode;
}
// 增加链表长度
size++;
}
}解读：
-
向链表中插入元素（尾插法）
java">public class Linked{
//添加元素(尾插法)
public void add(int val){
//获取当前链表的尾节点
final Node l = last ;
//创建新节点
final Node newNode = new Node(val);
if(l !=null){
//链表不为空
l.next = newNode;
}else{
//链表为空
first = newNode;
}
last = newNode;
size++;
}
}解读：
-
计算链表长度
java">public class Linked{
//返回链表长度
public int size(){
return size;
}
}解读：
- 返回链表的长度，即 size 变量的值；
-
重写toString()方法
java">public class Linked{
public String toString(){
//使用线程不安全，但性能较好的StringBuilder
StringBuilder ret = new StringBuilder();
//遍历链表
for(Node x =first;x !=null;x = x.next){
ret.append(x.val);
if(x.next !=null){
ret.append("->");
}
}
return ret.toString();
}
}解读：
-
测试类
javascript">public class LinkedTest {
public static void main(String[] args) {
//初始化链表1
Linked linked1 = new Linked();
linked1.add(1);
linked1.add(3);
linked1.add(5);
linked1.add(7);
linked1.addFirst(9);
System.out.println(linked1.size());
System.out.println(linked1.toString());
}
}-
测试结果
对链表的应用
2. 在自定义链表类的基础上，使用“双指针”实现两个链表的合并；
java"> //双指针合并两个单向链表
public static Linked meger(Linked l1 ,Linked l2 ){
//定义双指针，分别执行两个有序链表的头节点
Node p1 =l1.first, p2 = l2.first;
//用于保存合并结果的链表
Linked resultLinked = new Linked();
while(p1 !=null || p2 !=null){
if(p1 == null){
resultLinked.add(p2.val);
p2 = p2.next;
continue;
}
if(p2 == null){
resultLinked.add(p1.val);
p1 = p1.next;
continue;
}
//比较两个节点
if(p1.val < p2.val){
resultLinked.add(p1.val);
p1 = p1.next;
}else{
resultLinked.add(p2.val);
p2 = p2.next;
}
}
return resultLinked;
}解读：
- 接收两个参数 l1 和 l2，分别表示要合并的两个链表；
- 在方法内部定义两个指针 p1 和 p2，分别指向两个链表的头节点；
- 定义一个 Linked 对象 resultLinked 用于保存合并结果；
- 进入循环后会判断两个指针是否都指向 null，只要其中一个指针不为空就继续执行；
- 如果 p1 或 p2 任一个为 null，则直接将另一个链表剩余部分添加到 resultLinked 中，并移动指针到下一个节点；
- 如果两个节点都不为 null，则比较两个节点的值：如果 p1 的值小于 p2 的值，则将 p1 的值添加到 resultLinked 中，并将 p1 指针指向下一个节点；
- 如果 p2 的值小于等于 p1 的值，则将 p2 的值添加到 resultLinked 中，并将 p2 指针指向下一个节点；
- 循环结束后，返回合并后的链表 resultLinked；
时间复杂度为 O(m+n)，其中 m 和 n 分别表示两个链表的长度；
-
测试用例
java"> Linked linked2 =new Linked();
linked2.add(2);
linked2.add(4);
linked2.add(6);
linked2.add(8);
linked2.add(10);
//链表合并
Linked megerRet = Linked.meger(linked1, linked2);
System.out.println("合并结果"+megerRet);-
测试结果
3. 在自定义链表类的基础上，通过“栈”反转链表；
java"> public static Linked reverseLinked(Linked linked){
Stack<Node> nodeStack = new Stack<>();
//遍历链表，将所有Node节点，存入栈中
Node currentNode = linked.first;
if(currentNode ==null){
return linked;
}
while (currentNode !=null){
nodeStack.push(currentNode);
currentNode =currentNode.next;
}
//遍历栈，将栈中的Node节点，从栈顶依次出栈(逆序)，并存入链表中
linked = new Linked(); //清空原链表
while (!nodeStack.empty()){
linked.add(nodeStack.pop().val);
}
return linked;
}解读：
- 接收一个参数 linked，表示要逆序的链表；
- 创建一个 Stack 对象 nodeStack 用于存储链表的节点；
- 获取链表的头节点，并将其赋值给 currentNode；
- 如果链表为空，直接返回原链表，否则，通过循环遍历链表，将每个节点依次压入栈中，并将 currentNode 指针移动到下一个节点；
- 创建一个新的空链表对象 linked，用于存放逆序后的节点；
- 通过循环遍历栈中的节点，每次从栈顶取出一个节点，并将其值添加到 linked 链表中（此时节点的顺序已经逆序）；
- 循环结束后，返回逆序后的链表 linked；
时间复杂度为 O(n)，其中 n 表示链表的长度；
-
测试用例
java"> Linked linked1 = new Linked();
linked1.add(1);
linked1.add(3);
linked1.add(5);
linked1.add(7);
linked1.add(9);
linked1 = Linked.reverseLinked(linked1);
System.out.println("链表反转的结果"+linked1);-
测试结果
4. 在自定义链表类的基础上，计算两个大型整数(BigInteger)和；
java"> //用"链表"计算两个大型整数和
public static Linked addTwoNumber(Linked l1 ,Linked l2){
//从个位开始计算(链表的头部)
Node n1 =l1.first;
Node n2 =l2.first;
Linked retLinked = new Linked();
int carry = 0;//进位
while ( n1 != null || n2 !=null){
//分别获取当前计算的数字
int x =n1 != null ? n1.val :0;
int y =n2 != null ? n2.val :0;
int sum =x + y + carry;
//计算进位值
carry = sum /10;
//保存当前位计算结果
retLinked.add(sum %10);
if(n1 !=null){
n1 =n1.next;
}
if(n2 !=null){
n2 =n2.next;
}
}
if(carry !=0){
retLinked.add(carry);
}
retLinked= Linked.reverseLinked(retLinked);
return retLinked;
}解读：
- 接收两个参数 l1 和 l2，分别表示要相加的两个链表；
- n1 和 n2 分别表示链表 l1 和 l2 的头节点；
- 通过将 l1 和 l2 的头节点赋值给 n1 和 n2，开始从个位开始计算两个链表的和；
- 创建一个 Linked 对象 retLinked，用于存储计算结果；
- carry 表示进位的值，初始值为 0；
- 通过循环遍历链表中的节点，直到两个链表都遍历完；
- 在循环中，首先判断当前节点是否为空，如果不为空，则获取当前节点的值；如果为空，则将当前节点的值置为 0；
- 计算当前位的和（包括进位），并更新进位的值；
- 将当前位的和除以 10 取余数，并将余数添加到 retLinked 链表中作为当前位的计算结果；
- 如果链表节点不为空，则将当前节点指针移动到下一个节点；
- 在循环结束后，如果进位不为 0，则将进位值添加到 retLinked 链表的末尾；
- 最后，调用 Linked 类的静态方法 reverseLinked 将 retLinked 链表进行逆序操作；
- 返回逆序后的链表 retLinked，即两个大型整数(BigInteger)的和；
从个位开始逐位计算两个大型整数的和，并将结果保存在一个新的链表中。时间复杂度为 O(max(n, m))，其中 n 和 m 分别表示链表 l1 和 l2 的长度；
-
测试用例
java"> Linked linked3 = new Linked();
linked3.add(3);
linked3.add(4);
linked3.add(2);
Linked linked4 =new Linked();
linked4.add(1);
linked4.add(2);
linked4.add(3);
Linked linked = Linked.addTwoNumber(linked3, linked4);
linked3 =Linked.reverseLinked(linked3);
linked4 =Linked.reverseLinked(linked4);
System.out.printf("两数字%s,%s计算和:%s\n",linked3.toString(),linked4.toString(),linked.toString2());-
测试结果
5.1 在自定义链表类的基础上，使用"Set"集合 测试链表中是否存在环路现象；
java"> public static boolean hasCycle1(Node node){
HashSet<Node> nodeHashSet = new HashSet<>();
while (node !=null){
if(nodeHashSet.contains(node)){
return true;
}
nodeHashSet.add(node); //保存至Set
node = node.next;
}
return false;
}解读：
- 接收一个参数 node，表示链表的头节点；
- 创建一个 HashSet 对象 nodeHashSet，用于存储遍历过的节点；
- 通过循环遍历链表中的节点，直到遍历到链表末尾（node 为 null）或发现循环；
- 在循环中，首先检查当前节点是否已经存在于 nodeHashSet 中，如果存在则说明链表中存在循环，直接返回 true；
- 如果当前节点不在 nodeHashSet 中，则将当前节点添加到 nodeHashSet 中，并将指针移动到下一个节点；
- 如果遍历完整个链表后都没有发现循环，则返回 false，表示链表中不存在循环；
时间复杂度为 O(n)，其中 n 表示链表中节点的数量；
-
测试用例
java"> //判断链表中是否存在环路
Linked.Node node1 =new Linked.Node(1);
Linked.Node node2 =new Linked.Node(2);
Linked.Node node3 =new Linked.Node(3);
Linked.Node node4 =new Linked.Node(4);
Linked.Node node5 =new Linked.Node(5);
node1.next =node2;
node2.next =node3;
node3.next =node4;
node4.next =node5;
for(Linked.Node x =node1;x!=null;x =x.next){
System.out.print(x.val);
if(x.next !=null) {
System.out.print("=>");
}
}
System.out.println("是否存在环路:"+Linked.hasCycle1(node1));-
测试结果
5.2 在自定义链表类的基础上，基于"快慢指针"判断链表中是否存在环路；
java"> public static boolean hasCycle2(Node head){
//定义快慢指针
Node fast = head;
Node slow = head;
while (fast != null && fast.next != null && slow !=null){
fast =fast.next.next; //快指针每次移动2步
slow =slow.next; //慢指针每次移动1步
if(fast == slow){
return true;
}
}
return false; //链表无环
}解读：
- 接收一个参数 head，表示链表的头节点；
- 定义两个指针 fast 和 slow，初始时它们都指向链表的头节点 head；
- 通过循环遍历链表中的节点，直到快指针移动到链表末尾（fast 或 fast.next 为 null）；
- 在循环中，快指针每次向前移动两步（fast = fast.next.next），慢指针每次向前移动一步（slow = slow.next）；
- 在每次移动后，判断快指针是否与慢指针相遇，如果相遇则说明链表中存在循环，直接返回 true；
- 如果遍历完整个链表后快指针到达链表末尾仍未相遇，则返回 false，表示链表中不存在循环；
时间复杂度为 O(n)，其中 n 表示链表中节点的数量。这种方法在空间复杂度上优于使用 HashSet 存储节点的方法；
-
测试用例
java"> //判断链表中是否存在环路
Linked.Node node1 =new Linked.Node(1);
Linked.Node node2 =new Linked.Node(2);
Linked.Node node3 =new Linked.Node(3);
Linked.Node node4 =new Linked.Node(4);
Linked.Node node5 =new Linked.Node(5);
node1.next =node2;
node2.next =node3;
node3.next =node4;
node4.next =node5;
node5.next =node3; //存在环路
System.out.println("是否存在环路:"+Linked.hasCycle2(node2));-
测试结果
