资讯专栏INFORMATION COLUMN

Insertion Sort List,Merge Two Sorted Lists,Sort Li

Brenner / 863人阅读

摘要:解题思路题目很简单,就是要求用插入排序的方法来为链表排序。插入排序就是每次遍历一个新的元素,将其插入到前面已经排好序的元素中。但要注意我们要将的前一个节点记录下来在找到中点后,我们要将这样链表才能分割成个。

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.val

Merge 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.val

Sort 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

相关文章

  • [LintCode] Merge K Sorted Lists [DC/Heap]

    摘要:分治做法中,函数依然是将链表结点两两进行比较,然后在函数中迭代两个二分后的结果。 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, ...

    happyhuangjinjin 评论0 收藏0
  • 148. Sort List

    摘要:题目分析一看到问题,而且时间复杂度要求又是,很自然地就会想到数组时,如下这道题要求是,所以在上面的基础上还要进行一些额外操作找到的中点,使用快慢指针法。需要注意的是,找到中点后要把链表分成两段,即两个链表。这部分代码应该近似于这道题的答案。 Sort a linked list in O(n log n) time using constant space complexity. 题...

    anquan 评论0 收藏0
  • Sorting

    摘要:是稳定的排序,但是它需要额外的空间,时间复杂度为程序这个同上也是两个步骤,。最坏情况的时间复杂度为但是在实际情况中,通常是排序的最佳选择。就是有序的完全二叉树,所有我们要先根据已有的数组来建立一个。最后由后往前形成一个有序数组。 Bubble Sort就不说了,下面简单总结一个Selection Sort, Insertion Sort, Merge Sort和Quick Sort: ...

    calx 评论0 收藏0
  • [Leetcode] Merge Two Sorted Lists Merge K Sorted L

    摘要:注意因为堆中是链表节点,我们在初始化堆时还要新建一个的类。代码初始化大小为的堆拿出堆顶元素将堆顶元素的下一个加入堆中 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...

    stefanieliang 评论0 收藏0
  • 【LeetCode Easy】021 Merge Two Sorted Lists

    摘要:为减小空间复杂度,最后结果直接修改在上,不重新给分配空间。 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...

    icattlecoder 评论0 收藏0

发表评论

0条评论

Brenner

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<