数据结构基础：链表与栈

# 1. 数据结构概述

## 1.1 数据结构定义与作用

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，它包括了数据的组织、存储和管理方式。数据结构的设计关乎到算法的高效实现，因此对于计算机科学和软件工程领域具有极其重要的意义。

## 1.2 常见数据结构类型介绍

常见的数据结构类型主要包括数组、链表、栈、队列、树、图等。每种数据结构都有其独特的特点和适用场景，可以根据实际需求选择合适的数据结构来提高算法效率。

接下来，我们将深入探讨链表与栈这两种经典的数据结构。

# 2. 链表基础

链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据元素以及指向下一个节点的指针。链表相对于数组的优点是插入和删除操作更加高效，但查找元素需要遍历链表。

### 2.1 链表的概念与特点

链表是一种线性的数据结构，由一系列节点组成，每个节点包含数据元素以及指向下一个节点的指针。链表可以分为单向链表和双向链表两种形式。在单向链表中，每个节点只有指向下一个节点的指针；而在双向链表中，每个节点既有指向下一个节点的指针，又有指向前一个节点的指针。

链表的特点包括插入、删除操作高效，但查找操作需要遍历链表。链表的内存空间不需要连续，因此可以更灵活地分配内存。

### 2.2 单向链表与双向链表

#### 单向链表

单向链表中，每个节点包含一个数据元素和一个指向下一个节点的指针。单向链表的最后一个节点指向空（NULL）。

# Python 示例代码

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

# 创建单向链表
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

node1.next = node2
node2.next = node3

#### 双向链表

双向链表中，每个节点包含一个数据元素、一个指向下一个节点的指钩子和一个指向前一个节点的指钩子。

// Java 示例代码

class Node {
    int data;
    Node prev;
    Node next;

    public Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

// 创建双向链表
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);

node1.next = node2;
node2.prev = node1;
node2.next = node3;
node3.prev = node2;

### 2.3 链表的基本操作

链表的基本操作包括：遍历链表、查找节点、插入节点、删除节点等。这些操作是链表操作的基础，能够帮助我们实现更复杂的功能。

以上是关于链表基础的介绍，接下来我们将深入探讨链表高级应用。

# 3. 链表高级应用

链表是一种常见的数据结构，在实际的软件开发中有着广泛的应用。除了基本的增删改查操作外，链表还有许多高级的应用场景。在本章中，我们将深入探讨链表的高级应用，包括链表的逆置、链表的合并与拆分以及链表的环检测。让我们一起来了解这些有趣而实用的链表操作。

#### 3.1 链表的逆置

链表的逆置是指将链表中的节点顺序颠倒，即原来排在前面的节点会排到后面，反之亦然。实现链表逆置的算法有很多种，其中最经典的是使用迭代或递归的方式来实现。下面我们分别介绍这两种方法的实现。

##### 3.1.1 迭代法逆置链表

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

def reverse_linked_list(head):
    prev = None
    current = head
    while current:
        next_temp = current.next
        current.next = prev
        prev = current
        current = next_temp
    return prev

class ListNode {
    int value;
    ListNode next;

    ListNode(int value) {
        this.value = value;
    }
}

public ListNode reverseLinkedList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    while (current != null) {
        ListNode nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }
    return prev;
}

以上代码展示了使用迭代法逆置链表的实现。通过遍历链表，并在遍历过程中逐步改变节点的指向，最终实现了链表的逆置操作。

##### 3.1.2 递归法逆置链表

递归法是另一种实现链表逆置的经典方法，其实现方式如下：

def reverse_linked_list_recursive(head):
    if not head or not head.next:
        return head
    new_head = reverse_linked_list_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

public ListNode reverseLinkedListRecursive(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = reverseLinkedListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

以上代码展示了使用递归法逆置链表的实现。通过递归地调用函数，可以达到逆置链表的效果。

#### 3.2 链表的合并与拆分

除了链表的逆置操作，链表的合并与拆分也是常见的应用场景。链表的合并指的是将两个有序的链表合并成一个有序的链表，而链表的拆分则是将一个链表拆分成两个，通常是按照奇偶位置来拆分。下面我们分别介绍这两种操作的实现方法。

##### 3.2.1 链表的合并

链表的合并可以通过迭代或递归的方式来实现。以下为迭代法实现的示例代码：

def merge_sorted_lists(l1, l2):
    dummy = ListNode(0)
    current = dummy
    while l1 and l2:
        if l1.value < l2.value:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    current.next = l1 or l2
    return dummy.next

public ListNode mergeSortedLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    while (l1 != null && l2 != null) {
        if (l1.value < l2.value) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 =