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

简介:

PHP之从反向删除单链表元素的问题谈起
在完成一个单链表的删除指定元素的题目中,我发现了一件神奇的事情,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的算法题也真的是脑力的撸铁呢。

原文地址https://www.cnblogs.com/freephp/p/12593774.html

相关文章
|
Linux PHP
Linux查看和删除PHP版本
Linux查看和删除PHP版本
145 0
|
PHP
php php_strip_whitespace,php删除代码注释和空格
php php_strip_whitespace,php删除代码注释和空格
57 0
PHP:unset删除数组的元素
PHP:unset删除数组的元素
PHP:二维数组查找元素值并且返回下标
PHP:二维数组查找元素值并且返回下标
141 0
纯PHP代码最好在文件末尾删除 PHP 结束标记 ‘?>‘
纯PHP代码最好在文件末尾删除 PHP 结束标记 ‘?>‘
PHP:unset删除数组的元素
PHP:unset删除数组的元素
184 0
|
PHP
PHP如何获取前n个元素的数组
在上一篇文章《如何通过PHP查找给定字符串中的第一个非重复字符》中给大家介绍了怎么通过PHP查找给定字符串中的第一个非重复字符。感兴趣的朋友可以学习了解一下~ 那么本文将给大家介绍怎么获取前n个元素的数组,什么意思呢? 我们来看看具体的问题描述:如何编写一个PHP程序来获取一个数组,其中从给定数组的开头删除了n个元素。 还不明白也不要紧,我们直接看代码:
229 0
|
算法 PHP
PHP数组学习之使用冒泡算法对元素进行升序排序!
在之前的文章《PHP数组学习之返回给定两数间的全部公因数和最大公因数》中,我们介绍了利用数组方法返回给定两个整数a和b间的全部公因数和最大公因数的方法。这次我们进行PHP数组的学习,介绍一下利用PHP如何实现冒泡排序,使用冒泡算法怎么对数组元素进行升序排序。 首先我们来了解一下什么是冒泡算法(冒泡排序)? 冒泡排序(Bubble Sort),是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。 思想:
130 0
|
算法 PHP
PHP数组学习之比较数组元素,获取第一大和第二大值
在之前的文章中我们介绍了使用冒泡算法对数组元素进行升序排序的方法,感兴趣的可以点击链接进行查阅→《PHP数组学习之使用冒泡算法对元素进行升序排序!》。这次我们继续PHP数组学习系列,介绍一下比较数组元素,获取第一大和第二大值的方法。 本文的主题是:“给出一组数字,计算出它的最大值和第二大值”。
175 0
|
PHP
PHP快速实现删除空、制表符、换行符等特殊字符(两种方法)
上一篇文章《PHP数学函数实践四:将浮点数从零舍入到指定的小数位数》给大家介绍了怎么浮点数从零舍入到指定的小数位数,感兴趣的朋友可以了解学习一下~ 那么本文将给大家介绍解决一个在平时开发过程中非常常见的一个问题,就是如何从字符串中删除特殊字符! 在本文涉及到的特殊字符包括:空(“\0”)、水平制表符(“\t”) 、换行符(“\n”) 、垂直制表符(“\v” ) 和ESC(“\e”)。
338 0

相关产品