[链表专题]力扣21, 234

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 均按 非递减顺序 排列

思路 :双指针法

先判断list1，list2是否为空的三种情况，再按照双指针法依次将两个链表串起来.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;}
}