PHPer也刷《剑指Offer》之链表

温故知新

链表由一个一个的作为节点的对象构成的，每一个节点都有指向下一个节点的指针，最后一个节点的指针域指向空。每个节点可以存储任何数据类型。

根据类型可以分为单链表、双链表、环形链表、复杂链表等等结构，这些结构又可以相互组合。

对这部分基础内容不太熟悉的同学可以看我之前写的实战PHP数据结构基础之单链表以及实战PHP数据结构基础之双链表。

《剑指offer》中链表相关题目

俗话说光说不练假把式，既然学习了链表的基础概念和基本操作那我们一定要找些题目巩固下，下面来看《剑指offer》中的相关题目。

输入一个链表，从尾到头打印链表每个节点的值

题目分析：这道题还是比较简单的，考察的基础知识，难度系数一颗星。考察考点：链表。

解答示例：

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

输入一个链表，输出该链表中倒数第k个结点。

题目分析：依然考察的基础知识，难度系数一颗星。考察考点：链表。

解答示例：

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

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

题目分析：合并两个排序的链表，需要分别比较两个链表的每个值，然后改变next指针。考察考点：链表。

解答示例：

/*递归解法*/
/*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;
}

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

题目分析：保存相同的值，然后判断相同节点改变前一个节点的next指针即可。考察考点：链表。

解答示例：

/*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;
                }
                //头节点
                if (empty($prev)) {
                    $pHead = $currentNode;
                    $currentNode = $pHead;
                } else {
                    //正常节点
                    $prev->next = $currentNode;
                }
            } else {
                $prev = $currentNode;
                $currentNode = $currentNode->next;
            }
        }
    }
    return $pHead;
}

两个链表的第一个公共节点

解答示例：


/*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;
}

PHPer也刷《剑指Offer》之链表

温故知新

《剑指offer》中链表相关题目

更多题目解答