排序链表

落日映苍穹つ 2022-10-01 12:57 166阅读 0赞

## 题目描述 ##

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
    输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
    输出: -1->0->3->4->5

## 解法 ##

### 思路1，归并排序 ###

public ListNode sortList(ListNode head) { 
            
    	if(head == null || head.next==null) { 
    		return head;
    	}
    	
    	//获取中间节点
    	ListNode mid = findMid(head);
    	
    	//左右分别递归进行排序
    	ListNode right = sortList(mid.next);
    	mid.next =null;
    	ListNode left = sortList(head);
    	
    	//最终进行merge
    	return merge(left, right);
    }
    
    ListNode merge(ListNode firstNode, ListNode secondNode) { 
    	//哑结点
    	ListNode head = new ListNode(0);
    	ListNode cur = head, first = firstNode, second = secondNode;
    	while(first != null && second !=null) { 
    		while(first != null && first.val < second.val) { 
    			cur.next = first;
    			cur = cur.next;
    			first = first.next;
    		}
    		while(first != null && second !=null && first.val >= second.val) { 
    			cur.next = second;
    			cur = cur.next;
    			second = second.next;
    		}
    	}
    	if(first != null) { 
    		cur.next = first;
    	}else if (second !=null) { 
    		cur.next = second;
    	}
    	return head.next;
    }
    
    ListNode findMid(ListNode head) { 
    	ListNode slowNode = head, fastNode = head.next;
    	while(fastNode != null && fastNode.next!=null) { 
    		slowNode = slowNode.next;
    		fastNode = fastNode.next.next;
    	}
    	return slowNode;
    	
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，166人围观）

还没有评论，来说两句吧...

相关阅读

相关 148. 排序链表

题目来源 [148. 排序链表][148.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shado

朱雀/ 2023年02月20日 13:32/ 0 赞/ 169 阅读

相关排序链表

题目描述在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。示例 1: 输入: 4->2->1->3 输出: 1->2->3

落日映苍穹つ/ 2022年10月01日 12:57/ 0 赞/ 167 阅读

相关 java:链表排序

题目描述：Sort a linked list using insertion sort. 使用插入排序对链表进行排序 / Definition for sin

港控/mmm°/ 2022年06月17日 06:10/ 0 赞/ 149 阅读

相关链表排序--归并排序

要求在空间复杂度为O(1)的情况下对链表进行排序，在不考虑时间复杂度的情况下可以考虑冒泡排序，只对链表中的值进行操作，这样时间复杂度为O（n^2）。用归并排序，时间复杂度为O（

￡神魔★判官ぃ/ 2022年06月07日 07:10/ 0 赞/ 188 阅读

相关链表排序

链表排序代码 include <iostream> typedef struct node{ int data; stru

分手后的思念是犯贱/ 2022年05月27日 06:18/ 0 赞/ 178 阅读

相关链表17---链表排序

1、题目： Sort a linked list in O(n log n) time using constant space complexity. Example 1

逃离我推掉我的手/ 2022年05月25日 07:29/ 0 赞/ 182 阅读

相关链表的排序

![这里写图片描述][70] import java.util.; class ListNode { int val;

电玩女神/ 2022年05月23日 01:55/ 0 赞/ 163 阅读

相关单链表排序

算法思想：采用直接插入排序算法的思想，先构成只含一个数据结点的有序单链表，然后一次扫描剩下的结点p(直至p==NULL为止)，在有序表中通过比较查找插入p的前驱结点pre,然后

小咪咪/ 2022年05月08日 07:00/ 0 赞/ 220 阅读

相关链表排序-归并

链表排序，可以插入排序，我就不写了。实现归并排序归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Con

男娘i/ 2022年05月08日 06:06/ 0 赞/ 228 阅读

相关链表排序

前言：最近总结了一下针对只有头结点的单链表进行排序的几个简单的方法。交换节点：插入排序，冒泡排序，简单选择排序交换数据：快速排序初始化： i

你的名字/ 2022年03月27日 13:19/ 0 赞/ 236 阅读