什么网站可以有人做详情页个人网站怎么接广告

张

张建站

2026/4/7 20:34:36

10分钟阅读

什么网站可以有人做详情页,个人网站怎么接广告,做网站网站要找谁,免费的外链网站1.3 如何计算两个单链表所代表的数之和【出自 HW 笔试题】难度系数#xff1a;★★★☆☆ 题目描述#xff1a;被考察系数#xff1a;★★★★☆给定两个单链表#xff0c;链表的每个结点代表一位数#xff0c;计算两个数的和。例如#xff1a;输入链表 #xff08;3-&g…1.3 如何计算两个单链表所代表的数之和【出自 HW 笔试题】难度系数★★★☆☆ 题目描述被考察系数★★★★☆给定两个单链表链表的每个结点代表一位数计算两个数的和。例如输入链表 3- 1-5和链表5-9-2 输出 8-0-8即 513295808注意个位数在链表头。分析与解答方法一整数相加法主要思路分别遍历两个链表求出两个链表所代表的整数的值然后把这两个整数进行相加最后把它们的和用链表的形式表示出来。这种方法的优点是计算简单但是有个非常大的缺点当链表所代表的数很大的时候超出了 long int 的表示范围就无法使用这种方法了。方法二链表相加法主要思路对链表中的结点直接进行相加操作把相加的和存储到新的链表中对应的结点中同时还要记录结点相加后的进位。如下图所示使用这种方法需要注意以下几个问题 1每组结点进行相加后需要记录其是否有进位。 2如果两个链表 h1 与 h2 的长度不同长度分别为 L1 和 L2且 L1L2当对链表的第 L1 位计算完成后接下来只需要考虑链表 L2 剩余的结点的值需要考虑进位。 3对链表所有结点都完成计算后还需要考虑此时是否还有进位如果有进位则需要增加新的结点此结点的数据域为 1。实现代码如下/** * 对两个带头结点的单链表所代表的数相加 * param h1 第一个链表头结点 * param h2 第二个链表头结点 * return 相加后链表的头结点 */ fun addh1 LNode h2 LNode LNode { if h1.next null return h2 if h2.next null return h1 var c 0 //用来记录进位 var sum Int //用来记录两个结点相加的值 var p1 h1.next //用来遍历 h1 var p2 h2.next //用来遍历 h2 var tmp LNode //用来指向新创建的存储相加和的结点 val resultHead LNode //相加后链表头结点 resultHead.next null var p resultHead //用来指向链表 resultHead 最后一个结点 while p1 null p2 null { tmp LNode tmp.next null sum p1.data p2.data c tmp.data sum % 10 //两结点相加和 c sum / 10 //进位 p.next tmp p tmp p1 p1.next p2 p2.next } //链表 h2 比 h1 长接下来只需要考虑 h2 剩余结点的值 if p1 null { while p2 null { tmp LNode tmp.next null sum p2.data c tmp.data sum % 10 c sum / 10 p.next tmp p tmp p2 p2.next } } //链表 h1 比 h2 长接下来只需要考虑 h1 剩余结点的值 if p2 null { while p1 null { tmp LNode tmp.next null sum p1.data c tmp.data sum % 10 c sum / 10 p.next tmp p tmp p1 p1.next } } //如果计算完成后还有进位则增加新的结点 if c 1 { tmp LNode tmp.next null tmp.data 1 p.next tmp } return resultHead } fun mainargs ArrayString { var i 1 val head1 LNode head1.next null val head2 LNode head2.next null var tmp LNode var cur LNode head1 val addResult LNode //构造第一个链表 while i 7 { tmp LNode tmp.data i 2 tmp.next null cur.next tmp cur tmp i } cur head2 //构造第二个链表 i 9 while i 4 { tmp LNode tmp.data i tmp.next null cur.next tmp cur tmp i-- } printHead1 cur head1.next while cur null { print${cur.data} cur cur.next } print\nHead2 cur head2.next while cur null { print${cur.data} cur cur.next } addResult addhead1 head2 print\n 相加后 cur addResult.next while cur null { print${cur.data} cur cur.next } }程序的运行结果如下 Head1 3 4 5 6 7 8 Head2 9 8 7 6 5 相加后 2 3 3 3 3 9运行结果分析前五位可以按照整数相加的方法依次从左到右进行计算第五位 751进位的值为 3进位为 1。此时 Head2 已经遍历结束由于 Head1 还有结点没有被遍历所以依次接着遍历 Head1 剩余的结点 81进位9没有进位。因此运行代码可以得到上述结果。算法性能分析由于这种方法需要对两个链表都进行遍历因此时间复杂度为 ON其中 N 为较长的链表的长度由于计算结果保存在一个新的链表中因此空间复杂度也为 ON。1.4 如何对链表进行重新排序【出自 WR 笔试题】难度系数★★★☆☆ 题目描述被考察系数★★★★☆给定链表 L0-L1-L2 … Ln-1-Ln 把链表重新排序为 L0-Ln-L1-Ln-1- L2-Ln-2…。要求 1在原来链表的基础上进行排序即不能申请新的结点 2只能修改结点的 next 域不能修改数据域。分析与解答主要思路 1首先找到链表的中间结点。 2对链表的后半部分子链表进行逆序。 3把链表的前半部分子链表与逆序后的后半部分子链表进行合并合并的思路分别从两个链表各取一个结点进行合并。实现方法如下图所示实现代码如下 /** * 找出链表 Head 的中间结点把链表从中间断成两个子链表 * param head 链表头结点 * return 链表中间结点 */ private fun findMiddleNodehead LNode LNode { if head.next null return head var fast LNode head //遍历链表的时候每次向前走两步 var slow LNode head //遍历链表的时候每次向前走一步 var slowPre LNode head //当 fast 到链表尾时 slow 恰好指向链表的中间结点 while fast null fast.next null { slowPre slow slow slow.next fast fast.next.next } //把链表断开成两个独立的子链表 slowPre.next null return slow } /** * 方法功能对不带头结点的单链表翻转 * 输入参数 head链表头结点 */ private fun reversehead LNode LNode { if head.next null return head var pre LNode head //前驱结点 var cur head.next //当前结点 var next LNode //后继结点 pre.next null //使当前遍历到的结点 cur 指向其前驱结点 while cur null { next cur.next cur.next pre pre cur cur next } return pre } /** * 对链表进行排序 * param head 链表头结点 */ fun reorderhead LNode { if head.next null return //前半部分链表第一个结点 var cur1 LNode head.next val mid findMiddleNodehead.next //后半部分链表逆序后的第一个结点 var cur2 reversemid var tmp LNode //合并两个链表 while cur1.next null { tmp cur1.next cur1.next cur2 cur1 tmp tmp cur2.next cur2.next cur1 cur2 tmp } cur1.next cur2 } fun mainargs ArrayString { val head LNode head.next null var tmp LNode var cur LNode head //构造第一个链表 for i in 1..7 { tmp LNode tmp.data i tmp.next null cur.next tmp cur tmp } print排序前 cur head.next while cur null { print${cur.data} cur cur.next } reorderhead print\n 排序后 cur head.next while cur null { print${cur.data} cur cur.next } } 程序的运行结果如下排序前 1 2 3 4 5 6 7 排序后 1 7 2 6 3 5 4算法性能分析查找链表的中间结点的方法的时间复杂度为 ON逆序子链表的时间复杂度也为ON合并两个子链表的时间复杂度也为 ON因此整个方法的时间复杂度为 ON其中 N 表示的是链表的长度。由于这种方法只用了常数个额外指针变量因此空间复杂度为 O1。引申如何查找链表的中间结点分析与解答主要思路用两个指针从链表的第一个结点开始同时遍历结点一个快指针每次走 2 步另外一个慢指针每次走 1 步当快指针先到链表尾部时慢指针则恰好到达链表中部。快指针到链表尾部时当链表长度为奇数时慢指针指向的即是链表中间指针当链表长度为偶数时慢指针指向的结点和慢指针指向结点的下一个结点都是链表的中间结点上面的代码FindMiddleNode 就是用来求链表的中间结点的。1.5 如何找出单链表中的倒数第 k 个元素【出自 WR 笔试题】难度系数★★★☆☆ 题目描述被考察系数★★★★★找出单链表中的倒数第 k 个元素例如给定单链表 1-2-3-4-5-6-7则单链表的倒数第 k3 个元素为 5。分析与解答方法一顺序遍历两遍法主要思路首先遍历一遍单链表求出整个单链表的长度 n然后把求倒数第 k 个元素转换为求顺数第 n - k 个元素再去遍历一次单链表就可以得到结果。但是该方法需要对单链表进行两次遍历。方法二快慢指针法由于单链表只能从头到尾依次访问链表的各个结点因此如果要找链表的倒数第 k 个元素也只能从头到尾进行遍历查找在查找过程中设置两个指针让其中一个指针比另一个指针先前移 k 步然后两个指针同时往前移动。循环直到先行的指针值为 null 时另一个指针所指的位置就是所要找的位置。程序代码如下/** * 构造一个单链表 */ fun constructList LNode { val head LNode head.next null var tmp LNode var cur head //构造第一个链表 for i in 1..7 { tmp LNode tmp.data i tmp.next null cur.next tmp cur tmp } return head } /** * 顺序打印单链表结点的数据 */ fun printListhead LNode { var cur head.next while cur null { printcur.data.toString cur cur.next } } /** * 找出链表倒数第 k 个结点 * param head 链表头结点 * return 倒数第 k 个结点 */ fun findLastKhead LNode k Int LNode { if head.next null return head var slow LNode var fast LNode fast head.next slow fast var i 0 while i k fast null { //前移 k 步 fast fast.next i } //判断 k 是否已超出链表长度 if i k return null while fast null { slow slow.next fast fast.next } return slow } fun mainargs ArrayString { val head constructList //链表头指针 val result LNode print链表 printListhead result findLastKhead 3 if result null print\n 链表倒数第 3 个元素为 ${result.data} } 程序的运行结果如下链表 1 2 3 4 5 6 7 链表倒数第 3 个元素为 5算法性能分析这种方法只需要对链表进行一次遍历因此时间复杂度为 ON。另外由于只需要常量个指针变量来保存结点的地址信息因此空间复杂度为 O1。引申如何将单链表向右旋转 K 个位置题目描述给定单链表 1-2-3-4-5-6-7 k3 那么旋转后的单链表变为5-6-7-1-2-3-4。分析与解答主要思路 1首先找到链表倒数第 k1 个结点 slow 和尾结点 fast 如下图所示。 2把链表断开为两个子链表其中后半部分子链表结点的个数为 k。 3使原链表的尾结点指向链表的第一个结点。 4使链表的头结点指向原链表倒数第 k 个结点。实现代码如下 /** * 方法功能把链表右旋 k 个位置 */ fun rotateKhead LNode k Int { if head.next null return //fast 指针先走 K 步然后与 slow 指针同时向后走 var slow LNode var fast LNode val tmp LNode fast head.next slow fast var i 0 while i k fast null { //前移 K 步 fast fast.next i } //判断 k 是否已超出链表长度 if i k return //循环结束后 slow 指向链表倒数第 K1 个元素 fast 指向链表最后一个元素 while fast.next null { slow slow.next fast fast.next } tmp slow slow slow.next tmp.next null //如上图 2 fast.next head.next //如上图 3 head.next slow //如上图 4 } fun mainargs ArrayString { val head constructList print旋转前 printListhead rotateKhead 3 print\n 旋转后 printListhead }程序的运行结果如下旋转前 1 2 3 4 5 6 7旋转后 5 6 7 1 2 3 4算法性能分析这种方法只需要对链表进行一次遍历因此时间复杂度为 On。另外由于只需要几个指针变量来保存结点的地址信息因此空间复杂度为 O1。