Java LeetCode篇-深入了解关于单链表的经典解法

在数据结构中，单链表是一种常见的线性数据结构，其由一系列节点组成，每个节点包含数据和指向下一个节点的指针。在 LeetCode 上，单链表相关的问题种类繁多，例如反转链表、合并两个链表、寻找链表的中间节点等。在本篇文章中，我们将深入探讨一些经典的单链表解法，并通过代码示例来加深理解。

1. 反转链表

反转链表是一个经典问题。给定一个单链表的头节点，将链表反转，并返回反转后的链表头节点。

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

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 指针
        current = nextTemp;
    }
    return prev; // 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; // 返回合并后的链表头节点
}

3. 检测链表环

循环链表是链表中的一个重要概念。用快慢指针的方法可以有效地判断一个链表是否存在环。

public boolean hasCycle(ListNode head) {
    if (head == null) return false;

    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next; // 慢指针每次走一步
        fast = fast.next.next; // 快指针每次走两步

        if (slow == fast) { // 如果相遇，说明有环
            return true;
        }
    }
    return false; // 没有环
}

4. 找到链表的中间节点

这个问题要求我们找到链表的中间节点，可以使用快慢指针的方法，慢指针每次走一步，快指针每次走两步。

public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next; // 慢指针每次走一步
        fast = fast.next.next; // 快指针每次走两步
    }
    return slow; // 当快指针到达链表尾部时，慢指针正好到达中间节点
}

总结

以上是一些常见的单链表问题及其解决方案，这些问题在面试和算法竞赛中经常出现。掌握这些基本的链表操作不仅可以帮助我们解决许多问题，还能够提高我们的编程能力和思维方式。在解决链表问题时，理解链表的结构以及指针的移动极为重要，这会直接影响到代码的正确性和效率。希望本文能够帮助读者更好地理解单链表及其相关的经典解法。