链表头节点技巧与LeetCode83去重方法

目前golang学习网上已经有很多关于文章的文章了，自己在初次阅读这些文章中，也见识到了很多学习思路；那么本文《链表头节点：初始化与LeetCode 83去重技巧》，也希望能帮助到大家，如果阅读完后真的对你学习文章有帮助，欢迎动动手指，评论留言并分享~

本文深入探讨链表头节点（head）的概念、其在数据结构中的作用，以及在算法实现中如何正确处理其初始化与引用。以LeetCode 83“删除排序链表中的重复元素”为例，我们将分析原始解决方案的潜在问题，并提出一种更健壮、更符合最佳实践的代码实现，强调在遍历和修改链表时保留原始头节点引用的重要性。

链表头节点（Head）的本质与作用

在计算机科学中，链表是一种基本的数据结构，它由一系列相互连接的节点组成。每个节点通常包含两部分：存储的数据和指向下一个节点的引用（或指针）。链表的起点由一个特殊的节点标识，即“头节点”（head）。头节点是访问整个链表的唯一入口，通过它可以顺序遍历链表中的所有元素。从结构上看，head节点与链表中的其他节点并无本质区别，都是Node类（或ListNode类）的一个实例，但其作为链表起点的角色赋予了它特殊的重要性。

头节点的初始化与传入机制

关于头节点的初始化，一个常见的误解是它在处理链表的函数内部被创建。实际上，head节点通常是在链表被构建时，在调用处理链表的函数（例如deleteDuplicates）的代码之外进行初始化，并作为参数传递给这些函数。这意味着，当一个方法接收一个ListNode head作为参数时，它期望调用者已经提供了一个有效且已初始化的链表起点。

为了更清晰地说明这一点，以下是一个在标准Java环境中创建链表并调用处理函数的示例：

// 假设 ListNode 类已定义，包含 val 和 next 字段
// public class ListNode {
//     int val;
//     ListNode next;
//     ListNode() {}
//     ListNode(int val) { this.val = val; }
//     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
// }

public class Main {
    public static void main(String[] args) {
        // 在 main 方法中初始化一个链表：1 -> 1 -> 2 -> 3 -> 3
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(3);
        head.next.next.next.next = new ListNode(3);

        // 创建 Solution 类的实例并调用 deleteDuplicates 方法
        Solution solution = new Solution();
        ListNode distinctHead = solution.deleteDuplicates(head);

        // 打印去重后的链表，预期输出：1 -> 2 -> 3
        printList(distinctHead);
    }

    // 辅助方法：打印链表内容
    public static void printList(ListNode node) {
        while (node != null) {
            System.out.print(node.val + (node.next != null ? " -> " : ""));
            node = node.next;
        }
        System.out.println();
    }
}

// Solution 类将包含 deleteDuplicates 方法
class Solution {
    // ... deleteDuplicates 方法将在此处实现 ...
}

在这个例子中，head节点及其后续节点是在main方法中创建和链接的，形成一个完整的链表，然后才作为参数传递给deleteDuplicates方法。

LeetCode 83: 删除排序链表中的重复元素

LeetCode问题83要求我们从一个已排序的链表中删除所有重复的元素，确保每个元素只出现一次。

初始解决方案及其潜在问题：

以下是问题中提供的一个初始解决方案：

public ListNode deleteDuplicates(ListNode head) {
    if(head==null || head.next==null)return head;
    ListNode node=head; // 备份原始头节点
    while(head!=null && head.next!=null){ // 直接使用 head 进行遍历和修改
        if(head.val==head.next.val){
            head.next=head.next.next; // 删除重复节点
        }
        else head=head.next; // 移动到下一个节点
    }
    return node; // 返回备份的原始头节点
}

这个解决方案虽然能正确处理逻辑并返回去重后的链表，但其在循环中直接修改了作为方法参数传入的head变量来遍历链表。尽管在方法结束时通过返回node变量（它在开始时备份了原始head的引用）来保证了正确的结果，但这种直接修改传入参数的做法在软件工程中通常被视为不佳实践。它可能导致以下问题：

1. 副作用：函数修改了传入的参数，这可能与函数签名（deleteDuplicates(ListNode head)暗示操作一个链表，但可能不期望改变其原始引用）所表达的意图不符。
2. 可读性与维护性：在更复杂的场景或团队协作中，这种做法可能使代码难以理解，因为head在方法执行过程中其所指向的节点一直在变化，不再始终代表链表的起始。

优化与最佳实践：保持原始头节点引用

为了提高代码的清晰度、可读性和遵循“避免副作用”的最佳实践，我们应该避免直接修改作为方法参数传入的head引用。相反，我们可以创建一个新的局部变量作为遍历链表的指针。这样，原始的head引用将始终指向链表的起始位置，并且可以明确地作为方法的返回值。

优化后的实现：

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // 1. 处理基本情况：链表为空或只有一个节点，无需去重
        if (head == null || head.next == null) {
            return head;
        }

        // 2. 创建一个局部变量作为遍历指针，保留原始头节点引用
        //    currentNode 将用于遍历和修改链表，而 head 始终指向链表起点。
        ListNode currentNode = head;

        // 3. 遍历链表，直到 currentNode 或其下一个节点为空
        //    确保在访问 currentNode.next 时不会出现空指针异常
        while (currentNode != null && currentNode.next != null) {
            // 4. 检查当前节点和下一个节点的值是否相同
            if (currentNode.val == currentNode.next.val) {
                // 5. 如果相同，则删除下一个重复节点
                //    通过将当前节点的 next 指针跳过下一个重复节点，直接指向下下个节点。
                //    此时 currentNode 不移动，因为它可能还有更多与当前值相同的重复项紧随其后。
                currentNode.next = currentNode.next.next;
            } else {
                // 6. 如果不相同，则移动到下一个节点继续检查
                currentNode = currentNode.next;
            }
        }
        // 7. 循环结束后，返回原始的头节点。
        //    由于 head 引用从未被修改，它仍然指向去重后的链表的第一个节点。
        return head;
    }
}

代码解析：

1. 基本情况处理：首先检查链表是否为空或只包含一个节点。这两种情况都不需要进行去重操作，直接返回head即可。
2. 创建遍历指针：ListNode currentNode = head; 这一步是关键。我们创建了一个新的局部变量currentNode，它最初指向与head相同的节点。之后，所有对链表的遍历和修改都通过currentNode进行，而head变量本身的值（即它所引用的链表起始地址）在整个方法执行过程中保持不变。
3. 循环遍历：while (currentNode != null && currentNode.next != null) 循环条件确保currentNode和currentNode.next都是有效的节点，从而避免在访问currentNode.next时出现空指针异常。
4. 判断重复：if (currentNode.val == currentNode.next.val) 检查当前节点currentNode的值是否与其下一个节点currentNode.next的值相等。
5. 删除重复节点：如果值相等，说明currentNode.next是一个重复项。currentNode.next = currentNode.next.next; 这行代码将currentNode的next指针直接指向currentNode.next.next，从而有效地将currentNode.next从链表中移除。需要注意的是，此时currentNode不应该移动，因为可能存在多个连续的重复项（例如 1 -> 1 -> 1 -> 2），在删除一个重复项后，currentNode.next可能仍然指向一个与currentNode.val相同的节点，需要再次检查。
6. 移动到下一个节点：如果currentNode.val与currentNode.next.val不相等，说明currentNode.next不是重复项。此时，我们将currentNode向前移动一位，即currentNode = currentNode.next;，继续检查下一个节点对。
7. 返回原始头节点：当循环结束时，链表中的所有重复项都已被处理。由于head引用从未被修改，它仍然指向链表的第一个节点，该节点现在是去重后链表的起始。因此，直接返回head即可。

总结与注意事项

• 头节点的定义：head是链表的入口点，代表链表的第一个节点。
• 初始化位置：head通常在链表创建时初始化，并作为参数传入处理函数，而非在函数内部创建。
• 最佳实践：在链表操作（如遍历、修改）中，强烈建议使用一个独立的局部变量作为遍历指针（例如currentNode），以避免直接修改作为方法参数传入的原始head引用。这不仅提高了代码的清晰度、可读性，也避免了不必要的副作用，使函数行为更符合预期。
• LeetCode 83的启示：通过解决此问题，我们不仅掌握了链表去重算法的实现，更重要的是理解了在处理链表时，如何优雅且安全地管理头节点引用，这对于编写高质量的链表相关代码至关重要。

遵循这些原则，可以帮助开发者编写出更健壮、更易于理解和维护的链表操作代码。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《链表头节点技巧与LeetCode83去重方法》文章吧，也可关注golang学习网公众号了解相关技术文章。