双指针技巧在链表中的应用

## 第一章：链表数据结构概述

### 1.1 链表基本概念
链表是一种线性数据结构，它由一系列的节点组成，每个节点包含了数据和指向下一个节点的指针。相比于数组，链表的大小可以动态调整，而不需要提前分配固定大小的空间。本节将介绍链表的基本概念和特点。

### 1.2 链表的设计和使用
链表的设计和使用需要注意节点的添加、删除和遍历操作。本节将向读者展示如何设计和使用链表，包括链表的初始化、增加节点、删除节点和遍历节点的操作。

### 1.3 链表与数组的比较
链表和数组都是常见的数据结构，它们在存储和访问的方式上有着很大的区别。本节将比较链表和数组的优势和劣势，让读者了解它们在不同场景下的适用性。

// 示例代码：链表的定义和基本操作

class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedList {
    private ListNode head;
    
    public LinkedList() {
        head = null;
    }
    
    // 在链表末尾添加一个节点
    public void addNode(int val) {
        ListNode newNode = new ListNode(val);
        
        if (head == null) {
            head = newNode;
        } else {
            ListNode curr = head;
            
            while (curr.next != null) {
                curr = curr.next;
            }
            
            curr.next = newNode;
        }
    }
    
    // 删除指定值的节点
    public void deleteNode(int val) {
        if (head == null) {
            return;
        }
        
        if (head.val == val) {
            head = head.next;
            return;
        }
        
        ListNode curr = head;
        
        while (curr.next != null) {
            if (curr.next.val == val) {
                curr.next = curr.next.next;
                return;
            }
            
            curr = curr.next;
        }
    }
    
    // 遍历链表并打印节点值
    public void printList() {
        ListNode curr = head;
        
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        
        System.out.println();
    }
}

// 测试链表的基本操作
public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        
        list.addNode(1);
        list.addNode(2);
        list.addNode(3);
        
        list.printList();  // 输出：1 2 3
        
        list.deleteNode(2);
        
        list.printList();  // 输出：1 3
    }
}

本节介绍了链表的基本概念、设计和使用，以及与数组的比较。通过示例代码，读者可以更好地理解链表的操作和应用场景。在下一章节中，我们将介绍双指针技巧在链表中的应用。
## 第二章：双指针技巧介绍

双指针技巧是一种常见的算法解题方法，通过使用两个指针在结构化数据（如数组、链表等）中追逐动态问题的“热点”，从而简化问题的求解过程。本章将介绍双指针技巧的基本原理、应用场景以及在算法中的重要性。
第三章：在链表中使用双指针

### 3.1 快慢指针技巧

在链表中，快慢指针技巧是一种常用的技巧。它基于两个指针以不同的速度遍历链表，从而解决一些特定的问题。

快慢指针通常用于判断链表是否有环。快指针每次移动两步，慢指针每次移动一步，当链表中存在环时，快慢指针必定会相遇。

以下是使用快慢指针判断链表是否有环的示例代码（Python实现）：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val