实现php删除链表中重复的结点

1. 问题描述

需要实现一个PHP函数，用于删除链表中重复的节点。给定一个链表的头节点，函数应当返回删除重复节点后的链表的头节点。

2. 思路分析

为了解决这个问题，可以使用哈希表来存储节点的值，通过遍历链表，判断当前节点的值是否已经存在于哈希表中，如果存在则删除该节点，否则将节点的值添加到哈希表中，继续遍历下一个节点。最后返回删除重复节点后的链表的头节点。

3. 实现步骤

3.1 创建链表数据结构

首先，我们需要创建一个链表的数据结构，包含一个节点的值和指向下一个节点的指针。

class ListNode {
    public $val;
    public $next;
    
    public function __construct($val = 0) {
        $this->val = $val;
        $this->next = null;
    }
}

3.2 实现删除重复节点的函数

接下来，我们可以根据上面的思路实现删除重复节点的函数。

function deleteDuplicates($head) {
    if ($head === null) {
        return null;
    }
    
    $hashTable = array();
    $dummy = new ListNode(0);
    $dummy->next = $head;
    $prev = $dummy;
    $current = $head;
    
    while ($current !== null) {
        if (isset($hashTable[$current->val])) {
            $prev->next = $current->next;
        } else {
            $hashTable[$current->val] = true;
            $prev = $current;
        }
        
        $current = $current->next;
    }
    
    return $dummy->next;
}

3.3 测试函数的正确性

为了验证上面实现的函数的正确性，我们可以编写几个测试用例进行测试。

$head1 = new ListNode(1);
$node2 = new ListNode(2);
$node3 = new ListNode(3);
$node4 = new ListNode(3);
$node5 = new ListNode(4);
$node6 = new ListNode(4);
$node7 = new ListNode(5);
$head1->next = $node2;
$node2->next = $node3;
$node3->next = $node4;
$node4->next = $node5;
$node5->next = $node6;
$node6->next = $node7;
$result = deleteDuplicates($head1);
while ($result !== null) {
    echo $result->val . " ";
    $result = $result->next;
}

上面的测试用例中，链表的初始状态如下：

1->2->3->3->4->4->5

删除重复节点后的链表应该是：

1->2->5

4. 总结

通过使用哈希表来记录节点的值，我们可以轻松实现删除链表中重复节点的功能。这种方法的时间复杂度是O(n)，其中n是链表中的节点数。因为需要遍历整个链表一次，并且需要在哈希表中进行插入和查找操作。

通过使用哈希表，我们解决了删除链表中重复节点的问题，提高了算法的效率。