第一题：合并两个排序的链表
题目描述
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： 0 \le n \le 10000≤n≤1000，-1000 \le 节点值 \le 1000−1000≤节点值≤1000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：
或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：
示例
示例1
输入：{1,3,5},{2,4,6}
返回值：{1,2,3,4,5,6}
示例2
输入：{},{}
返回值：{}
示例3
输入：{-1,2,4},{1,3,4}
返回值：{-1,1,2,3,4,4}
题解
public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { // list1 list2为空的情况 if(list1==null) return list2; if(list2==null) return list1; if(list1 == null && list2 == null){ return null; } //将两个两个链表存放在list中 ArrayList<Integer> list = new ArrayList<>(); // 遍历存储list1 while(list1!=null){ list.add(list1.val); list1 = list1.next; } // 遍历存储list2 while(list2!=null){ list.add(list2.val); list2 = list2.next; } // 对 list 排序 Collections.sort(list); // 将list转换为 链表 ListNode newHead = new ListNode(list.get(0)); ListNode cur = newHead; for(int i=1;i<list.size();i++){ cur.next = new ListNode(list.get(i)); cur = cur.next; } // 输出合并链表 return newHead; } }
第二题：合并k个已排序的链表
描述
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
数据范围：节点总数 0 \le n \le 50000≤n≤5000，每个节点的val满足 |val| <= 1000∣val∣<=1000
要求：时间复杂度 O(nlogn)O(nlogn)
示例
示例1
输入：[{1,2,3},{4,5,6,7}]
返回值：{1,2,3,4,5,6,7}
示例2
输入：[{1,2},{1,4,5},{6}]
返回值：{1,1,2,4,5,6}
题解
import java.util.*; /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode mergeKLists(ArrayListlists) { // 采用分治进行合并链表 return mergeList( lists , 0 , lists.size() - 1 ); } // 分治进行链表两两合并 public ListNode mergeList(ArrayListlists , int L ,int R){ if(L == R){ return lists.get(L); } if(L > R){ return null; } int mid = L + ((R - L) >> 1); return merge( mergeList(lists,L,mid) , mergeList(lists,mid+1,R)); } // 合并两个链表，对比合并 public ListNode merge(ListNode l1 , ListNode l2){ if(l1 == null || l2 == null){ return l1 == null ? l2 : l1; } ListNode dummy = new ListNode(-1); ListNode cur = dummy; while( l1 != null && l2 != null){ if(l1.val < l2.val){ cur.next = l1; l1 = l1.next; }else{ cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = (l1 == null ? l2 : l1); return dummy.next; } }
第三题：判断链表中是否有环
题解描述
判断给定的链表中是否有环。如果有环则返回true，否则返回false。
数据范围：链表长度 0 \le n \le 100000≤n≤10000，链表中任意节点的值满足 |val| <= 100000∣val∣<=100000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
输入分为两部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。
例如输入{3,2,0,-4},1时，对应的链表结构如下图所示：
可以看出环的入口结点为从头结点开始的第1个结点（注：头结点为第0个结点），所以输出true。
示例
示例1
输入： {3,2,0,-4},1
返回值： true
说明：第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1（注：头结点为位置0），即-4->2存在一个链接，组成传入的head为一个带环的链表，返回true
示例2
输入： {1},-1
返回值： false
说明：第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false
示例3
输入： {-1,-7,7,-4,19,6,-9,-5,-2,-5},6
返回值： true
题解
.
public class Solution { public boolean hasCycle(ListNode head) { ListNode pos = head; // 哈希表记录访问过的结点 Set<ListNode> visited = new HashSet<ListNode>(); while (pos != null) { // 判断结点是否被访问 if (visited.contains(pos)) { return true; } else { // 结点记录添加到哈希表中 visited.add(pos); } // 遍历 pos = pos.next; } return false; } }
