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 $node
• @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