IT评测·应用市场-qidao123.com技术社区

标题: 链表知识回首 [打印本页]

作者: 立山 时间: 2025-4-17 09:28
标题: 链表知识回首
范例：单链表，双链表、循环链表

存储：在内存中不是连续存储

删除操作：即让c的指针指向e即可，无需开释d，由于java中又内存回收机制

添加节点：

链表的构造函数

public class ListNode {
// 结点的值
int val;
// 下一个结点
ListNode next;
// 节点的构造函数(无参)
public ListNode() {
}
// 节点的构造函数(有一个参数)
public ListNode(int val) {
this.val = val;
}
// 节点的构造函数(有两个参数)
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}

复制代码

可以直接用java自带的LinkedList类实现链表的初始化

import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
// 创建一个空的链表
LinkedList<Integer> list = new LinkedList<>();
// 向链表中添加元素
list.add(1);
list.add(2);
list.add(3);
// 打印链表内容
System.out.println(list);
}
}

复制代码

链表的声明：
Java标准库提供了LinkedList类，位于java.util包中。它的特点如下：

实现细节：LinkedList底层通常实现为双向链表，这意味着每个节点除了指向下一个节点，还保存对前一个节点的引用。
接口实现：除了实现List接口外，LinkedList还实现了Deque接口，使其既可以看成列表使用，也可以看成队列（或双端队列）使用。
增删操作：add(), remove(), offer(), poll()等方法在链表头尾插入或删除元素时性能较高。
遍历操作：由于链表没有下标索引，随机访问通常较慢。如果频繁使用随机访问，可以考虑使用ArrayList，ArrayList 底层是基于动态数组实现的

LinkedList<Integer> list = new LinkedList<Integer>();
List<Integer> list1 =new LinkedList<Integer>();
List<Integer> list2 =new ArrayList<>();
LinkedList list3 = new LinkedList();

复制代码

上述是常见的链表的声明方式
第一种，变量的声明范例和现实实现范例都是LinkedList，可直接调用 LinkedList 类中特有的方法，而且声明白泛型Integer，确保只能存储 Integer 范例的数据，编译期间就能举行范例检查，避免了范例转换非常。
第二种，声明范例是接口 List范例，现实实现的范例确实LinkedList，但只能调用 List 接口中定义的方法。如果必要使用 LinkedList 特有的方法（如队列或双端队列相关的方法），则必要显式地举行范例转换。同样使用了泛型 <Integer>，确保范例安全。
第三种声明范例是接口List，实现的是ArrayList范例，ArrayList 支持快速随机访问，时间复杂度为 O(1)。在数组中心插入或删除元素时必要移动元素，时间复杂度为 O(n)；而 LinkedList 在任意位置添加或删除（假如已经有相应节点引用）通常更高效。
第四种实现的是原始范例（由于没有使用泛型），编译器不会对聚会合的数据举行范例检查，
手搓链表

public class Linked {
static class Node{
int data;
Node next;
public Node(){};
public Node(int data){
this.data = data;
this.next =null;
}
}
public static class SingleLinkedList{
private Node head;
public void addFirst(int data){
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
public void addLast(int data){
Node newNode = new Node(data);
if(head ==null){
head = newNode;
return;
}
Node curr = head;
while(curr.next != null){
curr = curr.next;
}
curr.next = newNode;
}
public boolean remove(int data){
if(head == null){//若链表为空，则删除失败
return false;
}
if(head.data == data){//还要先判断头节点是否时要删除的
head = head.next;
return true;
}
Node curr = head;
while(curr.next != null && curr.next.data != data){
curr = curr.next;
}
if (curr.next != null) {
curr.next = curr.next.next;
return true;
}
return false;
}
public void printList() {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println("null");
}
}
public static void main(String[] args) {
SingleLinkedList list = new SingleLinkedList();
list.addFirst(4);
list.addFirst(3);
list.addFirst(2);
list.addFirst(1);
list.addLast(5);
list.addLast(6);
list.printList();//1 2 3 4 5 6 null
list.remove(6);
list.printList();//1 2 3 4 5 null
}
}

复制代码

反转链表

题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL，即右移

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
// 如果链表为空，则直接返回null
if(head == null){
return null;
}
// prev指针初始化为null，最后会成为反转后链表的头节点
ListNode prev = null;
// cur指针指向当前要处理的节点，开始时指向链表头head
ListNode cur = head;
// temp用于保存当前节点cur的下一个节点，防止在改变指针关系后丢失引用
ListNode temp = null;
// 当当前节点不为空时，循环执行反转操作
while (cur != null) {
// 保存cur的下一个节点，防止链表断裂
temp = cur.next; // 此时temp指向cur的下一节点
// 将当前节点的next指针指向前一个节点，实现局部反转
cur.next = prev; // 当前节点的next由原来的下一个节点变为前一个节点
// 将prev移动到当前节点位置，为下一次反转操作做准备
prev = cur;
// 将cur后移到下一个节点，也就是之前保存的temp
cur = temp;
}
// 循环结束后，prev指向反转后的链表头节点，返回它作为新的链表起点
return prev;
}
}

复制代码

链表内两两交换

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改背叛点内部的值，而是必要现实的举行节点交换。
解1：

创建一个虚拟头节点dummy指向head，定义current指针真相虚拟头节点
进入循环体内，确定current每次背面都能有两个节点举行交换操作
定义first和second分别指向第一个节点和第二个节点，
然后让第二个节点指向第一个节点，第一个节点指向下一个要交换的第一个节点，末了让current指向交换后的第一个节点
2，3，4循环操作，直至不敷节点互换退出循环，返回虚拟头节点之后的head

public class Solution {
public ListNode swapPairs(ListNode head) {
// 创建哑结点，它的 next 指向原链表的头
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode current = dummy;
// 循环条件：当前结点后面至少有两个节点
while (current.next != null && current.next.next != null) {
// 定义要交换的两个节点
ListNode first = current.next;
ListNode second = current.next.next;
// 交换节点：
// 1. 先将 first 指向 second 的下一个节点
first.next = second.next;
// 2. second 指向 first
second.next = first;
// 3. current 指向 second，完成与前面的连接
current.next = second;
// 移动 current，跳过刚才交换的两个节点
current = first;
}
// 返回哑结点的 next，即新的头节点
return dummy.next;
}
}

复制代码

解2：将链表转换为队列处理，在重修链表

import java.util.ArrayList;
import java.util.List;
public class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 1. 将链表节点存入数组
List<ListNode> nodes = new ArrayList<>();
ListNode current = head;
while (current != null) {
nodes.add(current);
current = current.next;
}
// 2. 在数组中交换相邻节点
for (int i = 0; i < nodes.size() - 1; i += 2) {
// 交换nodes[i]与nodes[i+1]
ListNode temp = nodes.get(i);
nodes.set(i, nodes.get(i+1));
nodes.set(i+1, temp);
}
// 3. 重建链表（根据交换后的数组重设每个节点的next指针）
for (int i = 0; i < nodes.size() - 1; i++) {
nodes.get(i).next = nodes.get(i + 1);
}
// 最后一个节点的next设为null
nodes.get(nodes.size() - 1).next = null;
// 4. 返回新的链表头（数组中第一个元素）
return nodes.get(0);
}
}

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)