系列博客目录
文章目录
理论知识
链表是数据结构中一种非常常见且基础的结构，在 Java 中，链表被广泛应用于解决动态数据存储问题。与数组不同，链表的元素（节点）并不需要在内存中是连续存储的，而是通过指针（或引用）将每个节点连接在一起。
基本概念
链表由一系列节点（Node）组成，每个节点通常包含两个部分：
- 数据域 (Data)：存储节点的数据。
- 指针域 (Next)：指向链表中的下一个节点。
链表的基本类型
-
单向链表 (Singly Linked List)：
- 每个节点包含一个指向下一个节点的引用。
- 头节点是链表的开始，尾节点的
next是null。
-
双向链表 (Doubly Linked List)：
- 每个节点有两个指针，一个指向下一个节点，一个指向前一个节点。
- 适用于需要频繁进行双向遍历的情况。
-
循环链表 (Circular Linked List)：
- 末尾节点指向头节点，形成一个环。
- 可以是单向链表或双向链表。
单向链表的基本结构
// 链表节点类
class Node {
int data; // 数据域
Node next; // 指针域，指向下一个节点
public Node(int data) {
this.data = data;
this.next = null;
}
}
// 单向链表类
class LinkedList {
Node head; // 链表的头节点
public LinkedList() {
this.head = null;
}
// 添加节点到链表末尾
public void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode; // 如果链表为空，直接让头节点指向新节点
} else {
Node current = head;
while (current.next != null) {
current = current.next; // 遍历到链表末尾
}
current.next = newNode; // 将最后一个节点的 next 指向新节点
}
}
// 在链表开头添加节点
public void prepend(int data) {
Node newNode = new Node(data);
newNode.next = head; // 新节点的 next 指向当前的头节点
head = newNode; // 更新头节点为新节点
}
// 删除指定节点
public void delete(int data) {
if (head == null) return;
if (head.data == data) {
head = head.next; // 删除头节点
return;
}
Node current = head;
while (current.next != null && current.next.data != data) {
current = current.next; // 遍历找到要删除的节点
}
if (current.next != null) {
current.next = current.next.next; // 删除当前节点的下一个节点
}
}
// 打印链表
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.printList(); // 输出: 10 20 30
list.prepend(5);
list.printList(); // 输出: 5 10 20 30
list.delete(20);
list.printList(); // 输出: 5 10 30
}
}
解释
- Node 类：代表链表的节点，包含数据和指向下一个节点的引用
next。 - LinkedList 类：表示链表本身，包含指向链表头部的引用
head。append：将新节点添加到链表末尾。prepend：将新节点添加到链表开头。delete：删除链表中指定值的节点。printList：打印链表的所有元素。
链表的基本操作
- 遍历：遍历链表从头到尾，访问每一个节点。
- 插入节点：在链表的头部、尾部或指定位置插入节点。
- 删除节点：从链表中删除某个指定值的节点。
- 查找节点：根据值查找节点的位置。
- 反转链表：将链表的节点顺序反转。
双向链表
双向链表中的每个节点都有两个引用：
- prev：指向前一个节点。
- next：指向下一个节点。
双向链表比单向链表有更多的灵活性，可以在两个方向上进行遍历。
class DoublyNode {
int data;
DoublyNode next;
DoublyNode prev;
public DoublyNode(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
DoublyNode head;
DoublyNode tail;
public DoublyLinkedList() {
this.head = null;
this.tail = null;
}
// 在链表末尾添加节点
public void append(int data) {
DoublyNode newNode = new DoublyNode(data);
if (tail == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
}
// 打印链表（从头到尾）
public void printList() {
DoublyNode current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
// 打印链表（从尾到头）
public void printReverse() {
DoublyNode current = tail;
while (current != null) {
System.out.print(current.data + " ");
current = current.prev;
}
System.out.println();
}
}
public class DoublyLinkedListDemo {
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
list.append(10);
list.append(20);
list.append(30);
list.printList(); // 输出: 10 20 30
list.printReverse(); // 输出: 30 20 10
}
}
双向链表的特点：
- 每个节点有两个引用：
next和prev，可以从头到尾或从尾到头进行遍历。 - 插入和删除操作比单向链表更高效，因为你不需要遍历到目标位置。
总结
- 单向链表：每个节点指向下一个节点，适用于只需要从头到尾遍历的情况。
- 双向链表：每个节点有两个指针，可以双向遍历，适用于需要双向遍历的场景。
- 循环链表：尾节点指向头节点，形成循环，适用于需要无限循环的情况。
链表的优势在于其动态大小和灵活的插入、删除操作，适用于需要频繁修改数据的情况，如实现队列、栈等数据结构。
例题
206.反转链表
链接
反转链表可以作为一种处理手段，在很多题目中进行应用。
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) {
ListNode lastNode = null;//最新的链表的头结点
ListNode nextNode;//原链表的下一个结点
while(head!=null){
nextNode = head.next;
head.next = lastNode;
lastNode = head;
head = nextNode;
}
return lastNode;
}
}
27.回文链表
链接
使用了反转链表进行处理。
class Solution {
public boolean isPalindrome(ListNode head) {
int count = 0;
ListNode curr = head;
while(curr != null){
count++;
curr = curr.next;
}
count = count / 2;
curr = head;
while(count > 0){
curr = curr.next;
count--;
}
ListNode reverse = reverseList(curr);
while(reverse != null){
if(reverse.val!=head.val){
return false;
}
reverse = reverse.next;
head = head.next;
}
return true;
}
public ListNode reverseList(ListNode head) {
ListNode lastNode = null;
ListNode nextNode;
while(head!=null){
nextNode = head.next;
head.next = lastNode;
lastNode = head;
head = nextNode;
}
return lastNode;
}
}
141.环形链表
链接
快慢指针
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) { //注意先判断fast == null
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/linked-list-cycle/solutions/440042/huan-xing-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
21.合并有序链表
链接
非常巧妙的递归方法。
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/merge-two-sorted-lists/solutions/226408/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
2.两数相加
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode head = null;
ListNode tail = null;
while(l1 != null || l2 != null){
int n1 = l1 == null ? 0 : l1.val;
int n2 = l2 == null ? 0 : l2.val;
int add =n1 + n2 + carry;
if(head == null){
head = tail = new ListNode(add%10);
}else {
tail.next = new ListNode(add%10);
tail = tail.next;
}
carry = add / 10;
if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;
}
if(carry>0){
tail.next = new ListNode(carry);
}
return head;
}
}
19.删除链表的倒数第 N 个结点
链接
tips：没有头结点可以自己创建一个头结点来简化问题。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode root = new ListNode();
root.next = head;
int count = n+1;
head = root;
ListNode res = head;
while(head!=null){
if(count>0){
count--;
}else {
res = res.next;
}
head = head.next;
}
res.next = res.next.next;
return root.next;
}
}
138.随机链表的复制
class Solution {
public Node copyRandomList(Node head) {
if(head == null) return null;
Node curr = head;
while(curr != null){
Node copy = new Node(curr.val);
copy.next = curr.next;
curr.next = copy;
curr = copy.next;
}
curr = head;
while(curr != null){
if(curr.random != null){
curr.next.random = curr.random.next;
}
curr = curr.next.next;
}
curr = head;
Node res = curr.next;
Node nextCopy;
Node copyNode;
Node next;
while(true){
next = curr.next.next;
if(next == null){
curr.next = null;
break;
}
copyNode = curr.next;
nextCopy = next.next;
curr.next = next;
copyNode.next = nextCopy;
curr = curr.next;
}
return res;
}
}