摘要：劍指中鏈表相關(guān)題目俗話說光說不練假把式，既然學(xué)習(xí)了鏈表的基礎(chǔ)概念和基本操作那我們一定要找些題目鞏固下，下面來看劍指中的相關(guān)題目。題目分析合并兩個(gè)排序的鏈表，需要分別比較兩個(gè)鏈表的每個(gè)值，然后改變指針。

鏈表由一個(gè)一個(gè)的作為節(jié)點(diǎn)的對(duì)象構(gòu)成的，每一個(gè)節(jié)點(diǎn)都有指向下一個(gè)節(jié)點(diǎn)的指針，最后一個(gè)節(jié)點(diǎn)的指針域指向空。每個(gè)節(jié)點(diǎn)可以存儲(chǔ)任何數(shù)據(jù)類型。

根據(jù)類型可以分為單鏈表、雙鏈表、環(huán)形鏈表、復(fù)雜鏈表等等結(jié)構(gòu)，這些結(jié)構(gòu)又可以相互組合。

對(duì)這部分基礎(chǔ)內(nèi)容不太熟悉的同學(xué)可以看我之前寫的實(shí)戰(zhàn)PHP數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之單鏈表以及實(shí)戰(zhàn)PHP數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之雙鏈表。

俗話說光說不練假把式，既然學(xué)習(xí)了鏈表的基礎(chǔ)概念和基本操作 那我們一定要找些題目鞏固下，下面來看《劍指offer》中的相關(guān)題目。

輸入一個(gè)鏈表，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值

題目分析：這道題還是比較簡(jiǎn)單的，考察的基礎(chǔ)知識(shí)，難度系數(shù)一顆星。
考察考點(diǎn)：鏈表。

解答示例：

function printListFromTailToHead($head)
{
    // write code here
    $list = [];
    $currentNode = $head;
    while ($currentNode) {
        $list[] = $currentNode->val;
        $currentNode = $currentNode->next;
    }
    return array_reverse($list);
}

輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。

題目分析：依然考察的基礎(chǔ)知識(shí)，難度系數(shù)一顆星。
考察考點(diǎn)：鏈表。

解答示例：

function FindKthToTail($head, $k)
{
    $currentNode = $head;
    $data = [];
    if ($currentNode) {
        while ($currentNode) {
            $data[] = $currentNode;
            $currentNode = $currentNode->next;
        }
        return $data[count($data) - $k];
    }
    return null;
}

輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。

題目分析：合并兩個(gè)排序的鏈表，需要分別比較兩個(gè)鏈表的每個(gè)值，然后改變next指針。
考察考點(diǎn)：鏈表。

解答示例：

/*遞歸解法*/
/*class ListNode{
    var $val;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}*/
function Merge($pHead1, $pHead2)
{
    if (is_null($pHead1)) {
        return $pHead2;
    } elseif (is_null($pHead2)) {
        return $pHead1;
    }
    $merged = new ListNode(null);
    if ($pHead1->val < $pHead2->val) {
        $merged->val = $pHead1->val;
        $merged->next = Merge($pHead1->next, $pHead2);
    } else {
        $merged->val = $pHead2->val;
        $merged->next = Merge($pHead1, $pHead2->next);
    }
    return $merged;
}

在一個(gè)排序的鏈表中，存在重復(fù)的結(jié)點(diǎn)，請(qǐng)刪除該鏈表中重復(fù)的結(jié)點(diǎn)，重復(fù)的結(jié)點(diǎn)不保留，返回鏈表頭指針。例如，鏈表1->2->3->3->4->4->5 處理后為 1->2->5

題目分析：保存相同的值，然后判斷相同節(jié)點(diǎn)改變前一個(gè)節(jié)點(diǎn)的next指針即可。
考察考點(diǎn)：鏈表。

解答示例：

/*class ListNode{
    var $val;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}*/
function deleteDuplication($pHead)
{
    $currentNode = $pHead;
    $prev = null;
    if ($currentNode) {
        while ($currentNode) {
            if ($currentNode->val == $currentNode->next->val) {
                $sameVal = $currentNode->val;
                while ($currentNode->val == $sameVal) {
                    $currentNode = $currentNode->next;
                }
                //頭節(jié)點(diǎn)
                if (empty($prev)) {
                    $pHead = $currentNode;
                    $currentNode = $pHead;
                } else {
                    //正常節(jié)點(diǎn)
                    $prev->next = $currentNode;
                }
            } else {
                $prev = $currentNode;
                $currentNode = $currentNode->next;
            }
        }
    }
    return $pHead;
}

兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)

解答示例：

/*class ListNode{
    var $val;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}*/
function FindFirstCommonNode($pHead1, $pHead2)
{
    $currentNode1 = $pHead1;
    $currentNode2 = $pHead2;
    if ($currentNode1 === $currentNode2) {
        return $pHead1;
    }
    while ($currentNode1 !== $currentNode2) {
        $currentNode1 = ($currentNode1 == null ? $pHead2 : $currentNode1->next);
        $currentNode2 = ($currentNode2 == null ? $pHead1 : $currentNode2->next);
    }
    return $currentNode1;
}

PHP基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)專題系列目錄地址：https://github.com/... 主要使用PHP語法總結(jié)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法。還有我們?nèi)粘HP開發(fā)中容易忽略的基礎(chǔ)知識(shí)和現(xiàn)代PHP開發(fā)中關(guān)于規(guī)范、部署、優(yōu)化的一些實(shí)戰(zhàn)性建議，同時(shí)還有對(duì)Javascript語言特點(diǎn)的深入研究。