学校网站设计实验报告,分类信息网站成都搭建,制作app软件公司,网站在政务新媒体建设方案1. 力扣2#xff1a;两数相加
1.1 题目#xff1a;
给你两个 非空 的链表#xff0c;表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的#xff0c;并且每个节点只能存储 一位 数字。
请你将两个数相加#xff0c;并以相同形式返回一个表示和的链表。
你可…1. 力扣2两数相加
1.1 题目
给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。
请你将两个数相加并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外这两个数都不会以 0 开头。 示例 1 输入l1 [2,4,3], l2 [5,6,4]
输出[7,0,8]
解释342 465 807.示例 2
输入l1 [0], l2 [0]
输出[0]示例 3
输入l1 [9,9,9,9,9,9,9], l2 [9,9,9,9]
输出[8,9,9,9,0,0,0,1]提示
每个链表中的节点数在范围 [1, 100] 内0 Node.val 9题目数据保证列表表示的数字不含前导零
1.2 思路
看注释比较简单。
1.3 题解
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {if(l1 null l2 null){return null;}ListNode p1 l1;ListNode p2 l2;// 两个指针从两个链表分别开始遍历// 将L1作为主链表while(p1 ! null p2 ! null){// 开始一轮遍历直接把L2的值加到L1上即可p1.val p1.val p2.val;// 如果L1的长小于等于L2则把L2多余的一段给L1if(p1.next null){p1.next p2.next;break;}p1 p1.next;p2 p2.next;}p1 l1;// 再次遍历如果遇到大于等于10的节点将这个节点的值-10// 如果这个点的下一个节点不为null则它的next节点1// 否则new一个节点即可while(p1 ! null){if(p1.val 10){p1.val - 10;if(p1.next ! null){p1.next.val 1;}else{p1.next new ListNode(1, null);}}p1 p1.next;}return l1;}
}
2. 力扣21合并两个有序链表
2.1 题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1 输入l1 [1,2,4], l2 [1,3,4]
输出[1,1,2,3,4,4]示例 2
输入l1 [], l2 []
输出[]示例 3
输入l1 [], l2 [0]
输出[0]提示
两个链表的节点数目范围是 [0, 50]-100 Node.val 100l1 和 l2 均按 非递减顺序 排列
2.2 思路
看注释题目也比较简单。
2.3 题解
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 特殊情况先列出来if(list1 null list2 null){return null;} else if(list1 null){return list2;}else if (list1 null){return list1;}ListNode dummy new ListNode(-1, null);ListNode p dummy;while(list1 ! null list2 ! null){if(list1.val list2.val){p.next list1;p p.next;list1 list1.next;}else{p.next list2;p p.next;list2 list2.next;}}// 如果list1和list2都为null此时走第一个if循环没啥问题if(list1 null){p.next list2;} else if (list2 null){p.next list1;}return dummy.next;}}
3. 力扣445两数相加2
3.1 题目:
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外这两个数字都不会以零开头。
示例1 输入l1 [7,2,4,3], l2 [5,6,4]
输出[7,8,0,7]示例2
输入l1 [2,4,3], l2 [5,6,4]
输出[8,0,7]示例3
输入l1 [0], l2 [0]
输出[0]提示
链表的长度范围为 [1, 100]0 node.val 9输入数据保证链表代表的数字无前导 0
进阶如果输入链表不能翻转该如何解决
3.2 思路
反转链表让数字高位变成低位然后低位开始相加。
3.3 题解
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {// 先将两个链表反转过来让高位变成低位l1 reverse(l1);l2 reverse(l2);ListNode p l1;// 同是数字低位才可以相加while(l1 ! null l2 ! null){l1.val l1.val l2.val;// 如果l1的长度小于等于L2// 把L2多余的部分接到L1上if(l1.next null){l1.next l2.next;break;}l1 l1.next;l2 l2.next;}ListNode p_copy p;// p_copy遍历链表把节点值超过10的值更新一下// 如果有下一个节点则把下一个节点的值1否则new一个节点while(p_copy ! null){if(p_copy.val 10){p_copy.val - 10;if(p_copy.next ! null){p_copy.next.val;}else{p_copy.next new ListNode(1, null);}}p_copy p_copy.next;}// 再反转链表把低位变成高位。return reverse(p);}// 反转链表方法private ListNode reverse(ListNode head) {// 新链表的哨兵节点ListNode dummy new ListNode(10086, null);// 头插法while(head ! null){ListNode p head.next;head.next dummy.next;dummy.next head;head p;}return dummy.next;}
}
4. 力扣2816翻倍以链表形式表示的数字
4.1 题目
你一个 非空 链表的头节点 head 表示一个不含前导零的非负数整数。
将链表 翻倍 后返回头节点 head 。
示例 1 输入head [1,8,9]
输出[3,7,8]
解释上图中给出的链表表示数字 189 。返回的链表表示数字 189 * 2 378 。
示例 2 输入head [9,9,9]
输出[1,9,9,8]
解释上图中给出的链表表示数字 999 。返回的链表表示数字 999 * 2 1998
提示
链表中节点的数目在范围 [1, 104] 内0 Node.val 9生成的输入满足链表表示一个不含前导零的数字除了数字 0 本身。
4.2 思路
看注释可以将整个链表和*2转化为将每个节点的值翻倍。然后再处理每个节点的值是否超过了10超过了则需要处理。
4.3 题解
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode doubleIt(ListNode head) {if(head null){return null;}// 将整个链表节点的和*2 - 将原链表的每个节点值*2ListNode p head;while(p ! null){p.val * 2;p p.next;}// 将链表倒置,为了让低位数字向高位数字进位head reverse(head);p head;// while循环处理每个节点的逻辑while(p ! null){if(p.val 10){p.val - 10;if(p.next ! null){p.next.val 1;}else{p.next new ListNode(1, null);}}p p.next;}// 整个链表处理完了再将链表倒置数字高位在链表前面head reverse(head);return head;}private ListNode reverse(ListNode head) {// 新链表的哨兵节点ListNode dummy new ListNode(10086, null);// 头插法while(head ! null){ListNode p head.next;head.next dummy.next;dummy.next head;head p;}return dummy.next;}
}
