首页 > 试题广场 > 链表排序
[编程题]链表排序
  • 热度指数:81996 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
在O(n log n)的时间内使用常数级空间复杂度对链表进行排序。
示例1

输入

{30,20,40}

输出

{20,30,40}

说明:本题目包含复杂数据结构ListNode,点此查看相关信息
思路:
因为题目要求复杂度为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;
    }
};

这里有更加详细的讲解:https://leetcode-cn.com/problems/sort-list/solution/148-pai-xu-lian-biao-bottom-to-up-o1-kong-jian-by-

编辑于 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)
数组存储的归并排序 时间复杂度O(nlogn)空间复杂度 O(n)
链表存储的归并排序 时间复杂度O(nlogn)空间复杂度 O(1)
发表于 2016-06-16 11:15:15 回复(1)
回顾一下常见排序算法及其时间复杂度,空间复杂度:


可以看出满足条件的只有堆排序以及归并排序,其他解析归并排序居多,我这里复习和使用堆排序方法。

复习一下堆排序相关知识:

1. 定义
什么叫做堆?
满足:1)堆中任意节点的值总是不大于(不小于)其子节点的值;
2)  堆总是一棵完全树。
常见的堆有二叉堆、左倾堆、斜堆、二项堆、斐波那契堆等等。
二叉堆是完全二叉树或者是近似完全二叉树,它分为两种:
最大堆:父结点的键值总是大于或等于任何一个子节点的键值;
最小堆:父结点的键值总是小于或等于任何一个子节点的键值。
那什么叫做完全二叉树(Complete Tree)?
完全二叉树: 除了最后一层之外的其他每一层都被完全填充,并且所有结点都保持向左对齐
满二叉树:除了叶子结点之外的每一个结点都有两个孩子,每一层(当然包含最后一层)都被完全填充
完满二叉树:除了叶子结点之外的每一个结点都有两个孩子结点。

我们将任意节点不大于其子节点的堆叫做最小堆小根堆,而将任意节点不小于其子节点的堆叫做最大堆大根堆最大堆通常被用来进行"升序"排序,而最小堆通常被用来进行"降序"排序。

二叉堆一般都通过"数组"来实现。数组实现的二叉堆,父节点和子节点的位置存在一定的关系。有时候,我们将"二叉堆的第一个元素"放在数组索引0的位置,有时候放在1的位置。当然,它们的本质一样(都是二叉堆),只是实现上稍微有一丁点区别。
假设"第一个元素"在数组中的索引为 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]重新调整为最大值。 依次类推,直到整个数列都是有序的。

以上概括源自
有时间可以仔细看一下。

所以思路就很清晰了,我们需要一个数列来实现一个二叉堆,然后完成初始化方法和堆的调整方法。
初始化方法也依赖于堆的调整方法,


下面上代码:

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题解的递归+归并解法,空间复杂度不能满足要求。
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)