文章目录
- 一、合并两个有序链表
- 题目描述
- 思路分析:
- 图示分析:
- AC代码
- 二、合并k个有序链表
- 题目描述
- 思路分析:
- 几点注意:
- 图示分析:
- AC代码
合并有序链表核心思路:
双指针:分别遍历两个链表,然后链到总的链表上。
模板:
ListNode head = new ListNode(-1);
ListNode prev = head;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
prev.next = list1;
list1 = list1.next;
} else {
prev.next = list2;
list2 = list2.next;
}
prev=prev.next;
}
prev.next=(list1==null)?list2:list1;
return head.next;
一、合并两个有序链表
题目描述
1.输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。OJ链接
思路分析:
- 比较两个链表当前引用的val值小的加入总的链,循环比较操作,循环条件是两个引用都不是空的,否则容易空指针异常。
- 循环终止的时候,肯定有一个结点不是空的这个时候我们需要单独操作,,然后让总的遍历的pre链上它
- 为了方便操作这里引用了一个虚拟头结点,返回的时候只要返回它的next值即可
图示分析:
AC代码
public ListNode Merge(ListNode list1, ListNode list2) {
ListNode head = new ListNode(-1);
ListNode prev = head;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
prev.next = list1;
list1 = list1.next;
} else {
prev.next = list2;
list2 = list2.next;
}
prev=prev.next;
}
prev.next=(list1==null)?list2:list1;
return head.next;
}
二、合并k个有序链表
题目描述
2.合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。OJ链接
思路分析:
- 给的顺序表,顺序表中的每个值是链表的每个头结点,所以循环条件是顺序表不为空
- 一个一个从表中拿出来,在调用我们之前定义的合并两个有序链表肯定行不通,这样不满足时间复杂度为O(nlogn),行不通。
几点注意:
- 注意导包
int mid = left + (right - left) /2;
可以通过,但是int mid = left + (right - left)>>1;
没办法通过,原因未知,以后再说。
图示分析:
AC代码
public ListNode mergeKLists(ArrayList<ListNode> lists) {
return divideMergeLists(lists,0,lists.size()-1);
}
private ListNode divideMergeLists(ArrayList<ListNode> lists, int left,int right) {
if (left > right) {
return null;
} else if (left == right) {
return lists.get(left);
}
int mid = left + (right - left) /2;
return Merge(divideMergeLists(lists, left, mid), divideMergeLists(lists, mid+1, right));
}
private ListNode Merge(ListNode list1, ListNode list2) {
ListNode head = new ListNode(-1);
ListNode prev = head;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
prev.next = list1;
list1 = list1.next;
} else {
prev.next = list2;
list2 = list2.next;
}
prev = prev.next;
}
prev.next = (list1 == null) ? list2 : list1;
return head.next;
}
最后
以上就是顺利灯泡最近收集整理的关于【DS】链表面试热题之合并链表及其变体的全部内容,更多相关【DS】链表面试热题之合并链表及其变体内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复