PHP之从反向删除单链表元素的问题谈起
2023-04-18 13:13:18 时间
在完成一个单链表的删除指定元素的题目中,我发现了一件神奇的事情,php对象赋值给另外一个变量后,可以如同引用传值一般继续利用新的变量来实现链表的链接。
后面经过查证后发现:
PHP7.0版本除了对象,资源之外,其余数据类型均已实现写时复制
尝试写了一个简单测试代码,如下所示:
<?php
$obj1 = new stdClass();
$obj1->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的算法题也真的是脑力的撸铁呢。
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击