在O(n log n)的时间内使用常数级空间复杂度对链表进行排序。
[编程题]链表排序
思路：
因为题目要求复杂度为O(nlogn),故可以考虑归并排序的思想。
归并排序的一般步骤为：
1）将待排序数组（链表）取中点并一分为二；
2）递归地对左半部分进行归并排序；
3）递归地对右半部分进行归并排序；
4）将两个半部分进行合并（merge）,得到结果。
所以对应此题目，可以划分为三个小问题：
1）找到链表中点 （快慢指针思路，快指针一次走两步，慢指针一次走一步，快指针在链表末尾时，慢指针恰好在链表中点）；
2）写出merge函数，即如何合并链表。 （见merge-two-sorted-lists 一题解析）
3）写出mergesort函数，实现上述步骤。
class Solution {
public:
ListNode* findMiddle(ListNode* head){
ListNode* chaser = head;
ListNode* runner = head->next;
while(runner != NULL && runner->next != NULL){
chaser = chaser->next;
runner = runner->next->next;
}
return chaser;
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == NULL){
return l2;
}
if(l2 == NULL){
return l1;
}
ListNode* dummy = new ListNode(0);
ListNode* head = dummy;
while(l1 != NULL && l2 != NULL){
if(l1->val > l2->val){
head->next = l2;
l2 = l2->next;
}
else{
head->next = l1;
l1 = l1->next;
}
head = head->next;
}
if(l1 == NULL){
head ->next = l2;
}
if(l2 == NULL){
head->next = l1;
}
return dummy->next;
}
ListNode* sortList(ListNode* head) {
if(head == NULL || head ->next == NULL){
return head;
}
ListNode* middle = findMiddle(head);
ListNode* right = sortList(middle->next);
middle -> next = NULL;
ListNode* left = sortList(head);
return mergeTwoLists(left, right);
}
};
发表于 2015-08-12 09:28:51
回复(29)
/*
考点：
1\. 快慢指针；2\. 归并排序。
此题经典，需要消化吸收。
复杂度分析:
T(n) 拆分 n/2, 归并 n/2 ，一共是n/2 + n/2 = n
/ \ 以下依此类推：
T(n/2) T(n/2) 一共是 n/2*2 = n
/ \ / \
T(n/4) ........... 一共是 n/4*4 = n
一共有logn层，故复杂度是 O(nlogn)
*/
class Solution {
public:
ListNode *sortList(ListNode *head) {
if (!head || !head->next) return head;
ListNode* p = head, *q = head->next;
while(q && q->next) {
p = p->next;
q = q->next->next;
}
ListNode* left = sortList(p->next);
p->next = NULL;
ListNode* right = sortList(head);
return merge(left, right);
}
ListNode *merge(ListNode *left, ListNode *right) {
ListNode dummy(0);
ListNode *p = &dummy;
while(left && right) {
if(left->val val) {
p->next = left;
left = left->next;
}
else {
p->next = right;
right = right->next;
}
p = p->next;
}
if (left) p->next = left;
if (right) p->next = right;
return dummy.next;
}
}; 由于题目要求空间复杂度为 O(1)，因此递归版本并不符合要求。下面给一下 bottom-to-up 的算法。
class Solution {
public:
ListNode* sortList(ListNode* head) {
ListNode dummyHead(0);
dummyHead.next = head;
auto p = head;
int length = 0;
while (p) {
++length;
p = p->next;
}
for (int size = 1; size < length; size <<= 1) {
auto cur = dummyHead.next;
auto tail = &dummyHead;
while (cur) {
auto left = cur;
auto right = cut(left, size); // left->@->@ right->@->@->@...
cur = cut(right, size); // left->@->@ right->@->@ cur->@->...
tail->next = merge(left, right);
while (tail->next) {
tail = tail->next;
}
}
}
return dummyHead.next;
}
ListNode* cut(ListNode* head, int n) {
auto p = head;
while (--n && p) {
p = p->next;
}
if (!p) return nullptr;
auto next = p->next;
p->next = nullptr;
return next;
}
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode dummyHead(0);
auto p = &dummyHead;
while (l1 && l2) {
if (l1->val < l2->val) {
p->next = l1;
p = l1;
l1 = l1->next;
} else {
p->next = l2;
p = l2;
l2 = l2->next;
}
}
p->next = l1 ? l1 : l2;
return dummyHead.next;
}
};
编辑于 2019-06-15 17:13:53
回复(36)
使用归并排序，链表的归并排序是O（1）复杂度.
public static ListNode sort(ListNode head){
if (head == null || head.next == null)
return head;
ListNode mid = getMiddle(head); //获取中间结点
//断开
ListNode midNext = mid.next;
mid.next = null;
//排序，合并
return mergeTwoLists(sort(head), sort(midNext));
}
/**
* 获取链表的中间结点,偶数时取中间第一个
* @param head
* @return
*/
public static ListNode getMiddle(ListNode head){
if (head == null || head.next == null) //空或只有一个
return head;
ListNode fast, slow; //快慢指针
fast = slow = head;
//快2步，慢一步
while (fast.next != null && fast.next.next != null) {
//偶数时取第一个
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
/**
* 实现合并两个已经排序的链表
* @param l1
* @param l2
* @return
*/
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//特殊情况
if (l1 == null)
return l2;
if (l2 == null)
return l1;
ListNode first = l1.next, second = l2.next;
ListNode res, newHead; //结果
if (l1.val < l2.val){
newHead = res = l1;
second = l2;
}else {
newHead = res = l2;
first = l1;
}
while (first != null || second != null){
if (first == null){ //第一条链表没了
res.next = second;
return newHead;
}
else if (second == null) { //第二条链表空了
res.next = first;
return newHead;
} else if (first.val < second.val){ //第一个值小
res.next = first;
first = first.next;
res = res.next;
} else {
res.next = second;
second = second.next;
res = res.next;
}
}
return newHead;
}
编辑于 2017-04-16 13:04:11
回复(5)
// 单链表的快速排序 时间复杂度O(nlogn),空间复杂度O(1)
public class Solution {
public ListNode sortList(ListNode head) {
quickSort(head, null);
return head;
}
public static void quickSort(ListNode head, ListNode end) {
if(head != end) {
ListNode partion = partion(head);
quickSort(head, partion);
quickSort(partion.next, end);
}
}
public static ListNode partion(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast != null) {
if(fast.val < head.val) {
slow = slow.next;
fast.val = slow.val ^ fast.val ^ (slow.val = fast.val);
}
fast = fast.next;
}
slow.val = head.val ^ slow.val ^ (head.val = slow.val);
return slow;
}
}
编辑于 2016-10-21 00:40:13
回复(10)
public class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode mid = getMid(head);
ListNode midNext = mid.next;
mid.next = null;
return mergeSort(sortList(head), sortList(midNext));
}
private ListNode getMid(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode slow = head, quick = head;
while(quick.next != null && quick.next.next != null) {
slow = slow.next;
quick = quick.next.next;
}
return slow;
}
private ListNode mergeSort(ListNode n1, ListNode n2) {
ListNode preHead = new ListNode(0), cur1 = n1, cur2 = n2, cur = preHead;
while(cur1 != null && cur2 != null) {
if(cur1.val < cur2.val) {
cur.next = cur1;
cur1 = cur1.next;
} else {
cur.next = cur2;
cur2 = cur2.next;
}
cur = cur.next;
}
cur.next = cur1 == null ? cur2 : cur1;
return preHead.next;
}
}
发表于 2017-06-18 00:49:45
回复(9)
思路扔是归并排序，递归实现，跟前面的都一样。
但是大家好像都会在归并的时候将归并好的放在新链表里，这会造成内存泄露。
好的方法是：归并的时候不要重新放在新链表，而是将右链表的元素都插入左链表中，
仍然在原来的链表中操作，可以杜绝了内存泄露的危险。具体看代码中的merge_list函数。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
//找到链表中间位置
ListNode *find_middle(ListNode *head)
{
//使用快，慢指针的方法：慢指针走一步，快指针走两步
ListNode *slow = head, *fast = head;
while(fast != NULL && fast->next != NULL && fast->next->next != NULL)
//第三个条件都满足才能++，否则对于两个元素不能平分
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
//合并两个有序链表：前提是两个链表本身必须有序
ListNode *merge_list(ListNode *&arg_left, ListNode *arg_right)
{
if(arg_right == NULL)
{
return arg_left;
}
ListNode *pre_left = arg_left;//左链表当前节点的上一个节点
ListNode *left = arg_left, *right = arg_right;
while(left != NULL && right != NULL)
{
if(left->val > right->val)
//为减少内存开辟，直接将右链表小值插入左链表中
{
if(left == arg_left)
//left位于左链表头结点
{
arg_left = right;
ListNode *tmp_right = right;
right = right->next;
tmp_right->next = left;
pre_left = tmp_right;
}
else
{
ListNode *tmp_right = right;
right = right->next;
pre_left->next = tmp_right;
tmp_right->next = left;
pre_left = tmp_right;
}
}
else
{
pre_left = left;
left = left->next;
}
}
if(left == NULL)
//如果左链表遍历完
{
pre_left->next = right;
}
return arg_left;
}
ListNode *sortList(ListNode *head) {
//归并排序
if(head == NULL || head->next == NULL)
//空链表或者只有一个元素
{
return head;
}
ListNode *middle = find_middle(head);//找到链表中间位置
ListNode *right = sortList(middle->next);
middle->next = NULL;
ListNode *left = sortList(head);
return merge_list(left, right);
}
};
发表于 2017-04-08 17:55:12
回复(0)
回顾一下常见排序算法及其时间复杂度，空间复杂度：
可以看出满足条件的只有堆排序以及归并排序，其他解析归并排序居多，我这里复习和使用堆排序方法。
复习一下堆排序相关知识：
1. 定义
什么叫做堆？
满足：1）堆中任意节点的值总是不大于(不小于)其子节点的值；
2) 堆总是一棵完全树。
2) 堆总是一棵完全树。
常见的堆有二叉堆、左倾堆、斜堆、二项堆、斐波那契堆等等。
二叉堆是完全二叉树或者是近似完全二叉树，它分为两种：
最大堆：父结点的键值总是大于或等于任何一个子节点的键值；
最大堆：父结点的键值总是大于或等于任何一个子节点的键值；
最小堆：父结点的键值总是小于或等于任何一个子节点的键值。
那什么叫做完全二叉树(Complete Tree)?
完全二叉树： 除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐。
满二叉树：除了叶子结点之外的每一个结点都有两个孩子，每一层(当然包含最后一层)都被完全填充。
完满二叉树：除了叶子结点之外的每一个结点都有两个孩子结点。
我们将任意节点不大于其子节点的堆叫做最小堆或小根堆，而将任意节点不小于其子节点的堆叫做最大堆或大根堆。最大堆通常被用来进行"升序"排序，而最小堆通常被用来进行"降序"排序。
二叉堆一般都通过"数组"来实现。数组实现的二叉堆，父节点和子节点的位置存在一定的关系。有时候，我们将"二叉堆的第一个元素"放在数组索引0的位置，有时候放在1的位置。当然，它们的本质一样(都是二叉堆)，只是实现上稍微有一丁点区别。
假设"第一个元素"在数组中的索引为 0 的话，则父节点和子节点的位置关系如下：
(01) 索引为i的左孩子的索引是 (2*i+1);
(02) 索引为i的左孩子的索引是 (2*i+2);
(03) 索引为i的父结点的索引是 floor((i-1)/2);
假设"第一个元素"在数组中的索引为 0 的话，则父节点和子节点的位置关系如下：
(01) 索引为i的左孩子的索引是 (2*i+1);
(02) 索引为i的左孩子的索引是 (2*i+2);
(03) 索引为i的父结点的索引是 floor((i-1)/2);
3. 堆排序的思路
1）初始化堆：将数列a[1...n]构造成最大堆。
2）交换数据：将a[1]和a[n]交换，使a[n]是a[1...n]中的最大值；然后将a[1...n-1]重新调整为最大堆。 接着，将a[1]和a[n-1]交换，使a[n-1]是a[1...n-1]中的最大值；然后将a[1...n-2]重新调整为最大值。 依次类推，直到整个数列都是有序的。
2）交换数据：将a[1]和a[n]交换，使a[n]是a[1...n]中的最大值；然后将a[1...n-1]重新调整为最大堆。 接着，将a[1]和a[n-1]交换，使a[n-1]是a[1...n-1]中的最大值；然后将a[1...n-2]重新调整为最大值。 依次类推，直到整个数列都是有序的。
以上概括源自
https://www.cnblogs.com/skywang12345/p/3610187.html https://www.cnblogs.com/skywang12345/p/3602162.html
有时间可以仔细看一下。
所以思路就很清晰了，我们需要一个数列来实现一个二叉堆，然后完成初始化方法和堆的调整方法。
初始化方法也依赖于堆的调整方法，
下面上代码：
public class Solution {
private static void swap(ListNode a, ListNode b) {
int tmp = a.val;
a.val = b.val;
b.val = tmp;
}
private static int len(ListNode head) {
int n = 0;
while(head!=null){
n++;
head = head.next;
}
return n;
}
class MaxHeap {
ListNode[] heap;
private int length;
MaxHeap(ListNode head){
length = len(head);
heap = new ListNode[length];
int i = 0;
while (head!=null){
heap[i++] = head;
head = head.next;
}
adjust();
}
// 从start节点开始，通过“下沉”来调整堆，如果一旦下移节点，换下去的节点就可能被破坏子节点最大堆性质，需要继续调整。
private void adjNodeDown(int start, int end){
ListNode curNode = heap[start];
int next = 2*start+1;
while (next <= end) {
if (next+1 <= end && heap[next+1].val > heap[next].val) {
next++;
}
if (curNode.val >= heap[next].val) {
break;
} else {
swap(curNode, heap[next]);
curNode = heap[next];
next = 2*next +1;
}
}
}
// 调整二叉堆为最大堆
private void adjust(){
if(length<2) return;
//从最后一个非叶子节点开始遍历，通过子节点对应父节点是floor((i-1)/2)推导得来
//从叶子节点开始遍历也可以，如果没有叶子节点就跳过去 int start = (length-2)/2;
while (start >= 0){
adjNodeDown(start--, length-1);
}
}
// 递增排序，依赖最大堆性质，每次取出根节点(最大值)往数组后面放，缩小堆大小并重新调整，获取新的最大值
ListNode sortAsc(){
int i = length-1;
while (i>0){
swap(heap[0], heap[i]);
adjNodeDown(0, --i);
}
return heap[0];
}
}
public ListNode sortList(ListNode head) {
if(head==null) return null;
MaxHeap maxHeap = new MaxHeap(head);
return maxHeap.sortAsc();
}
}
编辑于 2019-12-27 00:39:00
回复(0)
class Solution {
public:
ListNode *merge(ListNode *list1,ListNode *list2)
{
if(list1==nullptr)
return list2;
if(list2==nullptr)
return list1;
if(list1->val < list2->val)
{
list1->next = merge(list1->next,list2);
return list1;
}
else
{
list2->next = merge(list1,list2->next);
return list2;
}
}
ListNode *sortList(ListNode *head)
{
if(!head || !head->next)
return head;
ListNode *slow=head,*fast=head;
while(fast->next && fast->next->next)
{
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = nullptr;
slow = head;
ListNode *left = sortList(slow);
ListNode *right = sortList(fast);
return merge(left,right);
}
};
发表于 2017-07-03 22:36:37
回复(0)
ListNode* merge(ListNode *h1, ListNode *h2)
{
if(h1 == NULL) return h2;
else if(h2 == NULL) return h1;
else
{
ListNode *dummy = new ListNode(-1);
ListNode *p = dummy;
while(h1 && h2)
{
if(h1->val < h2->val)
{
p->next = h1;
h1 = h1->next;
}
else
{
p->next = h2;
h2 = h2->next;
}
p = p->next;
}
if(h1) p->next = h1;
if(h2) p->next = h2;
return dummy->next;
}
}
ListNode *sortList(ListNode *head) {
if(head == NULL || head->next == NULL)
return head;
// 时间复杂度为O(nlogn) 空间复杂度O(1)
// 可以用归并排序思想做
// 第一步：快慢指针找中点
ListNode *f = head, *s = head;
while(f->next && f->next->next)
{
f = f->next->next;
s = s->next;
}
// 注意前一半链表尾结点的next置NULL
f = s->next; // 后一半链表
s->next = NULL; // 前一半链表
ListNode *head1 = sortList(head);
ListNode *head2 = sortList(f);
// 第二步：归并
return merge(head1, head2);
}
编辑于 2016-04-21 00:22:11
回复(0)
public class Solution {
public ListNode sortList(ListNode head) {
if(head==null||head.next==null)
return head;
ListNode mid = getMid(head);
ListNode right = sortList(mid.next);
mid.next = null;
ListNode left = sortList(head);
return mergeSort(left, right);
}
private ListNode getMid(ListNode head){
ListNode temp = head.next;
ListNode mid = head;
while(temp!=null&&temp.next!=null){
mid = mid.next;
temp = temp.next.next;
}
return mid;
}
private ListNode mergeSort(ListNode left,ListNode right){
if(left==null)
return right;
if(right==null)
return left;
ListNode head = null;
if(left.val>right.val){
head = right;
right = right.next;
}else{
head = left;
left = left.next;
}
ListNode temp = head;
while(right!=null&&left!=null){
if(left.val>right.val){
temp.next = right;
right = right.next;
}else{
temp.next = left;
left = left.next;
}
temp = temp.next;
}
if(right!=null){
temp.next = right;
}
if(left!=null){
temp.next = left;
}
return head;
}
}
发表于 2016-05-30 14:26:03
回复(4)
leetcode中第148号题，其实我们学过的很多排序算法都需要使用数组的下标进行操作，而该题是链表，只有归并排序能满足要求
package go.jacob.day0525.linkedlist;
import go.jacob.day0520.链表问题.LinkedListOperate;
import go.jacob.day0520.链表问题.ListNode;
import static go.jacob.day0520.链表问题.LinkedListOperate.createLinkedList;
/**
* Sort a linked list in O(n log n) time using constant space complexity.
* <p>
* Example 1:
* <p>
* Input: 4->2->1->3
* Output: 1->2->3->4
* Example 2:
* <p>
* Input: -1->5->3->4->0
* Output: -1->0->3->4->5
* <p>
* 解法：
* 在链表上采用O(n log n)
* 很多排序算法都要按index查找元素
* 只有归并排序满足要求
*/
public class P148_SortList {
public static ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode preEnd = head, slow = head, fast = head;
while (fast != null && fast.next != null) {
preEnd = slow;
slow = slow.next;
fast = fast.next.next;
}
preEnd.next = null;//截断两个链表，不能用slow代替preEnd指针，因为slow记录了后半链表的头结点
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
return merge(l1, l2);
}
private static ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
cur = cur.next;
} else {
cur.next = l2;
l2 = l2.next;
cur = cur.next;
}
}
if (l1 != null)
cur.next = l1;
if (l2 != null)
cur.next = l2;
return dummy.next;
}
}
编辑于 2018-05-25 18:11:06
回复(1)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode sortList (ListNode head) {
// write code here
if(head == null || head.next == null) return head;
ListNode slow = head;
ListNode fast = head.next;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
ListNode tmp = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(tmp);
ListNode h = new ListNode(0);
ListNode res = h;
while(left != null && right != null){
if(left.val <= right.val){
h.next = left;
left = left.next;
} else {
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left != null ? left : right;
return res.next;
}
}
发表于 2020-10-24 21:39:48
回复(0)
参考LeetCode题解的递归+归并解法，空间复杂度不能满足要求。
官方题解可以参考一下：https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode sortList (ListNode head) {
if(head == null || head.next == null){
return head;
}
//定义快慢指针
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
//定义中间节点(切割点)
ListNode mid = slow.next;
//从中间将链表切开
slow.next = null;
//递归寻找左半边链表和右半边链表的中间节点
ListNode left = sortList(head);
ListNode right = sortList(mid);
//建立一个辅助节点作为头节点
ListNode h = new ListNode(0);
ListNode result = h;
//开始归并
while(left != null && right != null){
if(left.val < right.val){
h.next = left;
left = left.next;
}else{
h.next = right;
right = right.next;
}
h = h.next;
}
//将归并结束后的左右节点中不为空的那个节点添加到h上
//到此就完成了一次归并，递归操作会继续下次归并
h.next = left != null ? left : right;
//返回h作为头部的下个节点h.next。
return result.next;
}
}
发表于 2020-06-11 17:02:45
回复(0)
class Solution {
public:
// 自底向上的两路归并算法，非递归版
ListNode *dummyNode = new ListNode(-1); // 保存
ListNode *sortList(ListNode *head) {
// 构建一个空的头结点，以减少各类边界条件的判断，
// 能够方便地遍历和截断链表
ListNode *dn = new ListNode(-1), *prev = dn;
dn -> next = head;
int len = 0;
while (prev -> next != nullptr) {
prev = prev -> next;
len++;
}
prev = dn;
for (int i = 1; i < len; i *= 2) {
while (prev -> next != nullptr) {
ListNode *l1 = splitP(prev, i);
ListNode *l2 = splitP(prev, i);
ListNode *mergedHead = merge(l1, l2);
// 将合并的链表还原到原链表
dummyNode -> next -> next = prev -> next;
prev -> next = mergedHead;
prev = dummyNode -> next;
}
prev = dn;
}
delete dummyNode;
return dn -> next;
}
// 从head链表中截取从head -> next开始的size个结点，并返回其头结点
ListNode *splitP(ListNode *head, int size) {
int step = size;
ListNode *p = head -> next, *new_head;
while (--step && p != nullptr) {
p = p -> next;
}
new_head = head -> next;
if (p != nullptr) {
head -> next = p -> next;
p -> next = nullptr;
} else {
head -> next = nullptr;
}
return new_head;
}
// 合并两个链表，并返回合并后的新链表的头结点
ListNode *merge(ListNode* p1, ListNode *p2) {
ListNode *dummyHead = new ListNode(-1), *tail = dummyHead;
dummyHead -> next = nullptr;
ListNode *l1 = p1, *l2 = p2;
while (l1 != nullptr && l2 != nullptr) {
if (l1 -> val < l2 -> val) {
tail -> next = l1;
l1 = l1 -> next;
} else {
tail -> next = l2;
l2 = l2 -> next;
}
tail = tail -> next;
}
if (l1 != nullptr) tail -> next = l1;
if (l2 != nullptr) tail -> next = l2;
while (tail != nullptr) {
dummyNode -> next = tail;
tail = tail -> next;
}
return dummyHead -> next;
}
};
发表于 2020-04-07 21:49:53
回复(0)
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null) {
return null;
}
return mergeSort(head);
}
public ListNode mergeSort(ListNode head) {
if (head.next == null) {
return head;
}
ListNode pre = null;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
pre.next = null;
ListNode l1 = mergeSort(head);
ListNode l2 = mergeSort(slow);
return merge(l1, l2);
}
public ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
cur = cur.next;
l1 = l1.next;
} else {
cur.next = l2;
cur = cur.next;
l2 = l2.next;
}
}
if (l1 != null) {
cur.next = l1;
}
if (l2 != null) {
cur.next = l2;
}
return dummy.next;
}
}
发表于 2019-11-05 18:45:32
回复(0)
纪念第一次用 java 刷题：
public class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode leftHead = null, rightHead = null, curNode = head.next;
while(curNode != null){
ListNode next = curNode.next;
if(curNode.val < head.val){
if(leftHead != null){
curNode.next = leftHead;
leftHead = curNode;
}else{
leftHead = curNode;
curNode.next = null;
}
}else{
if(rightHead != null){
curNode.next = rightHead;
rightHead = curNode;
}else{
rightHead = curNode;
curNode.next = null;
}
}
curNode = next;
}
leftHead = sortList(leftHead);
rightHead = sortList(rightHead);
head.next = rightHead;
if(leftHead != null){
curNode = leftHead;
while(curNode.next != null){
curNode = curNode.next;
}
curNode.next = head;
}else{
leftHead = head;
}
return leftHead;
}
}
发表于 2019-10-05 11:01:01
回复(0)
public class Solution {
public ListNode sortList(ListNode head) {
if (head==null) return null;
return fen( head );
}
public ListNode bing(ListNode start,ListNode left)
{
ListNode s = start;
ListNode l = left;
ListNode node = null;
while(start!=null && left!=null)
{
if(start.val<=left.val) {
if(node!=null) node.next = start;
node = start;
start = start.next;
}else{
if(node!=null) node.next = left;
node = left;
left = left.next;
}
}
if(start==null) node.next=left;
if(left==null) node.next=start;
if (s.val<=l.val) return s;
return l;
}
public ListNode fen(ListNode node)
{
if(node.next==null) return node;
ListNode root = node.next;
node.next = null;
ListNode q = bing( node,fen( root ) );
return q;
}
}
我也不知道我的答案满不满足题意，反正我过了，嘿嘿
发表于 2019-07-17 14:55:23
回复(0)
参考前面两位大佬写的，有一些小毛病修正了一下
1、sortList函数中的head指针传进来需要先判断是否为空，或者下一节点是否为空，否则会发生段错误；
2、快慢指针寻找时，也要判断快慢指针是否为空，以及快指针下一节点是否为空；
class Solution {
public:
ListNode *sortList(ListNode *head) {
if(head == NULL || head->next == NULL)
return head;
ListNode* slow = head;
ListNode* fast = head->next;
while(fast!=NULL && fast->next!=NULL && slow != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
ListNode* left = sortList(slow->next);
slow->next = NULL;
ListNode* right = sortList(head);
return mergeTwoList(left,right);
}
ListNode *mergeTwoList(ListNode* left,ListNode *right)
{
ListNode* dummy = new ListNode(0);
ListNode* p = dummy;
while(left && right)
{
if (left->val > right->val)
{
p->next = right;
right = right->next;
}
else
{
p->next = left;
left = left->next;
}
p = p->next;
}
if (left == NULL)
p->next = right;
if (right == NULL)
p->next = left;
return dummy->next;
}
};
发表于 2019-04-16 14:12:43
回复(0)
问题信息
通过挑战的用户
查看代码-
2021-03-04 19:49:54
-
2021-03-04 17:08:12
-
2021-03-04 10:13:43
-
2021-03-03 20:58:10 -
2021-03-03 16:57:20
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客网公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802(电话) admin@nowcoder.com
- 牛客科技© All rights reserved
- 京ICP备14055008号-4 增值电信业务经营许可证
-
京公网安备 11010502036488号
