网站中的自助报价系统,怎么棋牌网站建设,一凡招聘 建筑人才网,上海聚通装修公司地址每道题后都有解析帮助你分析做题#xff0c;答案在最下面#xff0c;关注博主每天持续更新。 PS#xff1a;每道题解题方法不唯一#xff0c;欢迎讨论#xff01;
1.两数相加 题目描述 给你两个非空的链表#xff0c;表示两个非负的整数。它们每位数字都是按照逆序的方式… 每道题后都有解析帮助你分析做题答案在最下面关注博主每天持续更新。 PS每道题解题方法不唯一欢迎讨论
1.两数相加 题目描述 给你两个非空的链表表示两个非负的整数。它们每位数字都是按照逆序的方式存储的并且每个节点只能存储一位数字。 这两个数都不会以 0 开头。 请你将两个数相加并以相同形式返回一个表示和的链表。 示例 输入 l1 [123] l2 [456] 输出[479] 输入l1 [12]l2 [9] 输出[03] 解析 由于链表数字是逆序方式存储的所以两个链表对应节点值可以相加将它放入新的链表中。 但由于每个节点只能储存一位数字所以两个节点相加的值放入时需要l1.val v2.val) % 10创建一个变量carry (v1.val l2.val) / 10接受进位值。 在进行下面节点的时候carry参与运算放入新链表的值就变成l1.val l2.val carry) % 10, carry (l2.val l1.val carry) / 10。 如果两个链表的长度不同则可以认为长度短的链表的后面有若干个 0。 此外如果链表遍历结束后有carry 0,新链表的需要在添加一个值为carry的节点。 2. 删除链表倒数第N个节点 题目描述 给你一个链表删除链表倒数第N个节点并返回链表头节点。 示例 输入: head [12345]n 3 输出: [1245] 输入: head [123]n 3 输出: [23] 输入: head [ 1 ]n 1 输出: [] 解析 不知道你们看到这道题第一想法是什么我的第一想法就是前后双指针使用两个指针fast和slow一前一后遍历。 由于要删除倒数第n个节点所以fast先遍历当fast比slow快n个节点时两个指针同时遍历链表。 当fast指针的下一个节点为null时slow指针的下个节点刚好是要删除的节点这个时候只需要将slow.next指向slow.next.next即可。 注意一些特殊情况当fast指针先走时fast为null时说明删除节点不存在返回null当fast先走完时fast为null说明删除节点为头节点直接返回头节点的下一个节点。 3. 合并两个有序列表 题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 输入l1 [1,3,5], l2 [1,4,5] 输出[1,1,3,4,5,5] 输入l1 [], l2 [] 输出[] 输入l1 [], l2 [1] 输出[1] 解析 这题可以使用递归也可以迭代就是遍历两个链表一个一个比较。 这里我介绍一下递归 如果 l1 或者 l2 一开始就是空链表 那么没有任何操作需要合并所以我们只需要返回非空链表。否则我们要判断 l1 和 l2 哪一个链表的头节点的值更小然后递归地决定下一个添加到结果里的节点如l1.val l2.val; l1.next mergeTwoLists(l1.next,l2);如果两个链表有一个为空递归结束。 答案
1. 两数相加 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode head new ListNode(0);ListNode cur head;int count 0;while(l1 ! null l2 ! null){cur.next new ListNode(((l1.val l2.val count) % 10));count (l1.val l2.val count) / 10;cur cur.next;l1 l1.next;l2 l2.next;}while(l1 ! null){cur.next new ListNode((l1.val count) % 10);count (l1.val count) / 10;cur cur.next;l1 l1.next;}while(l2 ! null){cur.next new ListNode((l2.val count) % 10);count (l2.val count) / 10;cur cur.next;l2 l2.next;}if(count 0){cur.next new ListNode(count);}return head.next;}2. 删除链表倒数第N个节点 public ListNode removeNthFromEnd(ListNode head, int n) {ListNode slow head;ListNode fast head;for(int i 0;i n; i){if(fast null){return null;}fast fast.next;}if(fast null){return head.next;}while(fast.next ! null){fast fast.next;slow slow.next;}slow.next slow.next.next;return head;}3.合并两个有序列表 public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1 null){return list2;}else if(list2 null){return list1;}else{if(list1.val list2.val){list1.next mergeTwoLists(list1.next,list2);return list1;}else{list2.next mergeTwoLists(list1,list2.next);return list2;}}}
