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; } }
