数据结构——链表题型练习（java版）

链表是一种重要的线性数据结构，广泛应用于各类算法和数据处理。与数组相比，链表在插入和删除操作方面具有显著的优势。本文将通过一些链表题型的练习来加深对链表结构的理解，并结合Java代码示例进行讲解。

一、链表的基本概念

链表由一系列节点组成，每个节点包含数据域和指向下一个节点的指针（或引用）。链表的种类主要包括单链表、双链表和循环链表。

• 单链表：每个节点只有一个指针，指向下一个节点。
• 双链表：每个节点有两个指针，一个指向下一个节点，一个指向前一个节点。
• 循环链表：尾节点的指针指向头节点，形成一个环。

二、链表的基本操作

常见的链表操作包括插入节点、删除节点、查找节点等。以下是单链表的基本实现及相关操作。

1. 定义单链表节点

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

2. 创建链表

下面的代码示例展示了如何通过数组创建一个单链表。

public ListNode createLinkedList(int[] nums) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    for (int num : nums) {
        current.next = new ListNode(num);
        current = current.next;
    }
    return dummy.next;
}

3. 打印链表

打印链表中的每个节点数据，方便查看链表内容。

public void printLinkedList(ListNode head) {
    ListNode current = head;
    while (current != null) {
        System.out.print(current.val + " ");
        current = current.next;
    }
    System.out.println();
}

三、链表的常见题型

1. 反转链表

反转链表是一个经典题目，要求将链表的顺序翻转。下面是反转链表的Java实现。

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;

    while (current != null) {
        ListNode nextTemp = current.next; // 保存下一个节点
        current.next = prev; // 反转指针
        prev = current; // 移动 prev 指针
        current = nextTemp; // 移动 current 指针
    }
    return prev; // 返回新的头节点
}

2. 合并两个有序链表

合并两个已经排序的链表，保持排序顺序。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    // 连接剩余节点
    if (l1 != null) {
        current.next = l1;
    } else {
        current.next = l2;
    }

    return dummy.next;
}

四、总结

链表作为一种基本的数据结构，其灵活性和高效性使得它在编程中具有重要作用。通过反转链表、合并链表等例题的练习，我们不仅加深了对链表操作的理解，也为解决更多复杂的问题打下了基础。在实际开发中，掌握链表数据结构的运用能够帮助我们更高效地处理数据，提升程序的性能。希望通过本文的讲解，能够帮助读者更好地理解链表及其相关操作。