视频网站建设公司,浙江建设银行网站,网站设计制作哪里好,东莞中企动力做网站1. 力扣21 : 合并两个有序链表
题 :
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1#xff1a;输入#xff1a;l1 [1,2,4], l2 [1,3,4]
输出#xff1a;[1,1,2,3,4,4]
示例 2#xff1a;输入#xff1a;l…1. 力扣21 : 合并两个有序链表
题 :
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 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 100
l1 和 l2 均按 非递减顺序 排列
思路 :双指针法
先判断list1list2是否为空的三种情况再按照双指针法依次将两个链表串起来.head记录头指针的位置.p指针起到串联的作用.
解 :
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 null list2 null) {return null;}if (list1 null) {return list2;}if (list2 null) {return list1;}ListNode p;if (list1.val list2.val) {p list2;list2 list2.next;} else {p list1;list1 list1.next;}ListNode head p;while (list1 ! null list2 ! null) {if (list1.val list2.val) {p.next list2;p p.next;list2 list2.next;} else {p.next list1;p p.next;list1 list1.next;}}if (list1 null) {p.next list2;} else {p.next list1;}return head;}
}
2. 力扣234 : 回文链表
题 :
给你一个单链表的头节点 head 请你判断该链表是否为
回文链表
。如果是返回 true 否则返回 false 。示例 1输入head [1,2,2,1]
输出true
示例 2输入head [1,2]
输出false提示链表中节点数目在范围[1, 105] 内
0 Node.val 9进阶你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题
思路 : 辅助数组 双指针
借助辅助数组从而判断数组是否是回文数组.该解法空间复杂度较高O(n).但时间复杂度为O(n).
解 :
class Solution {public boolean isPalindrome(ListNode head) {if (head null || head.next null) {return true;}ListNode p head;int count 0;while (p ! null) {count;p p.next;}int[] a new int[count];p head;count 0;while (p ! null) {a[count] p.val;p p.next;}boolean flag true;int last count - 1;int hed 0;for (int i count / 2; i 0; i--) {if (a[hed] ! a[last--]) {flag false;}}return flag;}
}
