资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/PHPer也刷《剑指Offer》之链表

PHPer也刷《剑指Offer》之链表

daydream / 934人阅读

摘要：剑指中链表相关题目俗话说光说不练假把式，既然学习了链表的基础概念和基本操作那我们一定要找些题目巩固下，下面来看剑指中的相关题目。题目分析合并两个排序的链表，需要分别比较两个链表的每个值，然后改变指针。

温故知新

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

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

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

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

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

</>复制代码 
  1. 输入一个链表，从尾到头打印链表每个节点的值

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

解答示例：

</>复制代码 
  1. function printListFromTailToHead($head)
  2. {
  3.     // write code here
  4.     $list = [];
  5.     $currentNode = $head;
  6.     while ($currentNode) {
  7.         $list[] = $currentNode->val;
  8.         $currentNode = $currentNode->next;
  9.     }
  10.     return array_reverse($list);
  11. }
</>复制代码 
  1. 输入一个链表，输出该链表中倒数第k个结点。

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

解答示例：

</>复制代码 
  1. function FindKthToTail($head, $k)
  2. {
  3.     $currentNode = $head;
  4.     $data = [];
  5.     if ($currentNode) {
  6.         while ($currentNode) {
  7.             $data[] = $currentNode;
  8.             $currentNode = $currentNode->next;
  9.         }
  10.         return $data[count($data) - $k];
  11.     }
  12.     return null;
  13. }
</>复制代码 
  1. 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

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

解答示例：

</>复制代码 
  1. /*递归解法*/
  2. /*class ListNode{
  3.     var $val;
  4.     var $next = NULL;
  5.     function __construct($x){
  6.         $this->val = $x;
  7.     }
  8. }*/
  9. function Merge($pHead1, $pHead2)
  10. {
  11.     if (is_null($pHead1)) {
  12.         return $pHead2;
  13.     } elseif (is_null($pHead2)) {
  14.         return $pHead1;
  15.     }
  16.     $merged = new ListNode(null);
  17.     if ($pHead1->val < $pHead2->val) {
  18.         $merged->val = $pHead1->val;
  19.         $merged->next = Merge($pHead1->next, $pHead2);
  20.     } else {
  21.         $merged->val = $pHead2->val;
  22.         $merged->next = Merge($pHead1, $pHead2->next);
  23.     }
  24.     return $merged;
  25. }
</>复制代码 
  1. 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

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

解答示例：

</>复制代码 
  1. /*class ListNode{
  2.     var $val;
  3.     var $next = NULL;
  4.     function __construct($x){
  5.         $this->val = $x;
  6.     }
  7. }*/
  8. function deleteDuplication($pHead)
  9. {
  10.     $currentNode = $pHead;
  11.     $prev = null;
  12.     if ($currentNode) {
  13.         while ($currentNode) {
  14.             if ($currentNode->val == $currentNode->next->val) {
  15.                 $sameVal = $currentNode->val;
  16.                 while ($currentNode->val == $sameVal) {
  17.                     $currentNode = $currentNode->next;
  18.                 }
  19.                 //头节点
  20.                 if (empty($prev)) {
  21.                     $pHead = $currentNode;
  22.                     $currentNode = $pHead;
  23.                 } else {
  24.                     //正常节点
  25.                     $prev->next = $currentNode;
  26.                 }
  27.             } else {
  28.                 $prev = $currentNode;
  29.                 $currentNode = $currentNode->next;
  30.             }
  31.         }
  32.     }
  33.     return $pHead;
  34. }
</>复制代码 
  1. 两个链表的第一个公共节点

解答示例：

</>复制代码 
  1. /*class ListNode{
  2.     var $val;
  3.     var $next = NULL;
  4.     function __construct($x){
  5.         $this->val = $x;
  6.     }
  7. }*/
  8. function FindFirstCommonNode($pHead1, $pHead2)
  9. {
  10.     $currentNode1 = $pHead1;
  11.     $currentNode2 = $pHead2;
  12.     if ($currentNode1 === $currentNode2) {
  13.         return $pHead1;
  14.     }
  15.     while ($currentNode1 !== $currentNode2) {
  16.         $currentNode1 = ($currentNode1 == null ? $pHead2 : $currentNode1->next);
  17.         $currentNode2 = ($currentNode2 == null ? $pHead1 : $currentNode2->next);
  18.     }
  19.     return $currentNode1;
  20. }
更多题目解答

PHP基础数据结构专题系列目录地址：https://github.com/... 主要使用PHP语法总结基础的数据结构和算法。还有我们日常PHP开发中容易忽略的基础知识和现代PHP开发中关于规范、部署、优化的一些实战性建议，同时还有对Javascript语言特点的深入研究。

GPU云服务器 云服务器 phper 也刷题 剑指 offer

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/28902.html

相关文章

  • 利用PHP实现《剑指 offer》之链表（数据结构与算法实战 ）

    摘要：一定要认真看分析注释题目要求题目描述输入一个链表，从尾到头打印链表每个节点的值。分析因为链表只有知道当前结点才能知道下一结点，所以不可能直接从后往前打印。 一定要认真看 分析 | 注释 | 题目要求 Question 1 题目描述：输入一个链表，从尾到头打印链表每个节点的值。 分析：因为链表只有知道当前结点才能知道下一结点，所以不可能直接从后往前打印。这种逆序的算法（策略）我们常用栈这...

    hiYoHoo 评论0 收藏0

  • PHPer面试必看：分门别类带你撸《剑指Offer》之二叉树

    摘要：例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。操作给定的二叉树，将其变换为源二叉树的镜像。剑指中还有一道类似的变种题目，就是下面的这道，之字形遍历二叉树。最后下面的两道题目分别运用了二叉树先序中序遍历算法。 开篇 以下内容可能偏应试但很好理解，所以大家一定要坚持看下去，因为我们变强的过程注定孤独的，坚持下来就会看到明天的太阳。 回顾 showImg(https://user-...

    li21 评论0 收藏0

  • 剑指offer系列——剑指 Offer 24. 反转链表（C语言）

    摘要：假设反转对象节点为，反转指向的结点为，反转后指向的结点为首结点。当然也可以根据栈先进后出的特点，使用栈反转链表。 ⭐️前面的话⭐️ 大家好！博主开辟了一个新的专栏—...

    weakish 评论0 收藏0

  • 剑指offer系列——剑指 Offer 06. 从尾到头打印链表（C语言）

    摘要：导航小助手剑指从尾到头打印链表题目详情解题思路源代码总结剑指从尾到头打印链表题目详情输入一个链表的头节点，从尾到头反过来返回每个节点的值用数组返回。时间复杂度方法先反转链表并求长度，在将反转后的链表数据拷贝至数组中。 ...

    DevTTL 评论0 收藏0

发表评论

登陆后可评论

0条评论

daydream

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<