亲宝软件园·资讯

展开

PHP之从反向删除单链表元素的问题谈起

freephp 人气:0
在完成一个单链表的删除指定元素的题目中,我发现了一件神奇的事情,php对象赋值给另外一个变量后,可以如同引用传值一般继续利用新的变量来实现链表的链接。 后面经过查证后发现: > PHP7.0版本除了对象,资源之外,其余数据类型均已实现写时复制 尝试写了一个简单测试代码,如下所示: ``` val = 3; $obj1->next = null; $obj2 = $obj1; $obj2->next = array(); $obj2 = null; var_dump($obj1); ``` 打印出的$obj1的结构里面不会因为$obj2被赋值为null而让$obj1成为null。 关于从后往前面删除单链表元素的问题,原题如下: 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5. 说明: 给定的 n 保证是有效的。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list 分析下来就是一个基础单链表操作的变种题目,如果是从头往后删除的话,就是我们常见的删除操作。所以唯一不同的就是顺序问题,于是先定义获取单链表长度的函数和删除指定位置元素的函数,然后再调用的时候把从后往前的位置数改为从头往后数的位置即可。 ``` /** * Definition for a singly-linked list. * class ListNode { * public $val = 0; * public $next = null; * function __construct($val) { $this->val = $val; } * } */ class Solution { /** * @param ListNode $head * @param Integer $n * @return ListNode */ function removeNthFromEnd($head, $n) { $length = getLength($head); $from_start_num = $length - $n; // if ($n == 1 && $length == 1) { // return null; // } // if ($from_start_num == 0 && $n === $length) { // return $head->next; // } $return_node_list = deleteLinkItem($head, $from_start_num); return $return_node_list; } } /** * @param $head * @param int $index * @return null */ function deleteLinkItem($head, $index = 1) { if (is_null($head)) { return null; } else { if ($index == 0) { return $head->next; } $i = 1; $current = $head; while($current->next != null) { if ($i == $index) { $tmp = $current->next; break; } $i++; $current = $current->next; } $current->next = $tmp->next; return $head; } } /** * @param $head * @param $node * @param int $index * @return mixed */ function getLength($head) { if (empty($head)) { return 0; } $i = 1; while($head->next != null) { $i++; $head = $head->next; } return $i; } ``` 唯一要注意的是,由于deleteLinkItem的$index是从1开始算的,和脚标起始0不同,假如是要删除0下标(也就链表是第一个元素被删除),那么直接返回头部节点的next即可,如代码中的这段: ``` if ($index == 0) { return $head->next; } ``` 总的来说解法中规中矩,没有利用的PHP的黑魔法。越是自由度高的编程语言,对于算法题来说越难真正锻炼到,所以往往需要自废神功,当成静态语言去玩。而下标看得让人脑仁疼,看来即使是一道medium的算法题也真的是脑力的撸铁呢。

加载全部内容

相关教程
猜你喜欢
用户评论