摘要:解题思路题目很简单,就是要求用插入排序的方法来为链表排序。插入排序就是每次遍历一个新的元素,将其插入到前面已经排好序的元素中。但要注意我们要将的前一个节点记录下来在找到中点后,我们要将这样链表才能分割成个。
Insertion Sort List
Sort a linked list using insertion sort.
1.解题思路
题目很简单,就是要求用插入排序的方法来为链表排序。插入排序就是每次遍历一个新的元素,将其插入到前面已经排好序的元素中。
因为头结点没法确定,所以我们用一个dummy节点;然后开始向后逐个遍历,当前遍历的节点为cur,另外sortnode每次都指向已经排好序的第一个节点dummy,然后从dummy开始往后,直到找到sortnode.next.val>=cur.val,则表示cur节点要插到有序链表的sortnode后面。
2.代码
public class Solution { public ListNode insertionSortList(ListNode head) { if(head==null||head.next==null) return head; ListNode dummy=new ListNode(0); ListNode cur=head; while(cur!=null){ ListNode sortnode=dummy; while(sortnode.next!=null&&sortnode.next.valMerge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.1.解题思路
合并两个有序链表,同样需要构造一个Dummy节点。
1)考虑特殊情况,如果有一个链表为空,则直接返回另一个链接;
2)利用两个指针p,q遍历两个链表,如果都不为空,则循环继续;
3)使用node指向新链表的最后一个节点,初始化为dummy
4) 比较p,q的数值的大小,如果p小于q,则把p加到node.next,并且node赋值为p,而p指针需要前进一个;
5) 结束循环时,check一下是否还有链表中有剩余元素,并将剩余元素加入到新链表node指针的后面。2.代码
public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1==null) return l2; if(l2==null) return l1; ListNode dummy=new ListNode(0); ListNode p=l1; ListNode q=l2; ListNode node=dummy; while(p!=null&&q!=null){ if(p.valSort List
Sort a linked list in O(n log n) time using constant space complexity.
1.解题思路
题目要求时间复杂度为O(n log n),所以我们就想到用归并排序,自然就想到和上一题的mergeTwoLists。
但要做mergeTwoLists,必须得先将当前的list分割成两个List,所以采用递归实现。
要分割链表,最简单的办法就是找到中点,那很明显是利用slow,fast来实现,最后slow就是链表的中间点。但要注意我们要将Slow的前一个节点记录下来pre,在找到中点后,我们要将pre.next=null,这样链表才能分割成2个。
2.代码public class Solution { public ListNode sortList(ListNode head) { if(head==null||head.next==null) return head; ListNode slow=head,fast=head,pre=null; while(fast!=null&&fast.next!=null){ pre=slow; slow=slow.next; fast=fast.next.next; } pre.next=null; ListNode l1=sortList(head); ListNode l2=sortList(slow); return mergeTwoSortedList(l1,l2); } private ListNode mergeTwoSortedList(ListNode l1,ListNode l2){ if(l1==null) return l2; if(l2==null) return l1; ListNode dummy=new ListNode(0); ListNode p=l1; ListNode q=l2; ListNode node=dummy; while(p!=null&&q!=null){ if(p.val
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/69826.html
摘要:分治做法中,函数依然是将链表结点两两进行比较,然后在函数中迭代两个二分后的结果。 Problem Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example Given lists: [ 2->4->null, null, ...
摘要:题目分析一看到问题,而且时间复杂度要求又是,很自然地就会想到数组时,如下这道题要求是,所以在上面的基础上还要进行一些额外操作找到的中点,使用快慢指针法。需要注意的是,找到中点后要把链表分成两段,即两个链表。这部分代码应该近似于这道题的答案。 Sort a linked list in O(n log n) time using constant space complexity. 题...
摘要:注意因为堆中是链表节点,我们在初始化堆时还要新建一个的类。代码初始化大小为的堆拿出堆顶元素将堆顶元素的下一个加入堆中 Merge Two Sorted Lists 最新更新请见:https://yanjia.me/zh/2019/01/... Merge two sorted linked lists and return it as a new list. The new list...
摘要:为减小空间复杂度,最后结果直接修改在上,不重新给分配空间。 Easy 021 Merge Two Sorted Lists Description: Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes o...
阅读 2279·2021-11-25 09:43
阅读 2827·2021-11-24 09:39
阅读 2895·2019-08-30 11:10
阅读 1064·2019-08-29 16:34
阅读 564·2019-08-29 13:25
阅读 3332·2019-08-29 11:21
阅读 2826·2019-08-26 11:39
阅读 2362·2019-08-26 11:34