当前位置：首页 > news >正文

链表知识回顾

news 来源：原创 2025/8/23 3:25:13

类型：单链表，双链表、循环链表

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

删除操作：即让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 nulllist.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) {// 如果链表为空，则直接返回nullif(head == null){return null;}// prev指针初始化为null，最后会成为反转后链表的头节点ListNode prev = null;// cur指针指向当前要处理的节点，开始时指向链表头headListNode 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后移到下一个节点，也就是之前保存的tempcur = 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 指向 firstsecond.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设为nullnodes.get(nodes.size() - 1).next = null;// 4. 返回新的链表头（数组中第一个元素）return nodes.get(0);}
}

类型：单链表，双链表、循环链表

手搓链表

反转链表

链表内两两交换

相关文章：