首页 > 试题广场 >

链表排序

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

输入

{30,20,40}

输出

{20,30,40}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
Java
詆調壹點头像 詆調壹點 
// 单链表的快速排序 时间复杂度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)
牛客6342235号头像 牛客6342235号 
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)
LinuX18头像 LinuX18 
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)
LEarBB头像 LEarBB 
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)
Java
LiberHome头像 LiberHome 
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)
Java
Kinggj头像 Kinggj
利用归并排序；依次递归：1）找到中间节点  2）左右分支各自排序  3）合并两个有序链表 
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 mid = findMidList(head);
        //断开
        ListNode midNext = mid.next;
        mid.next=null;
        return mergeList(sortList(head),sortList(midNext));
    }
    public ListNode findMidList(ListNode h){
        if(h==null || h.next==null) return h;
        ListNode l1 =h;
        ListNode l2 =h;
        while(l2.next!=null && l2.next.next!=null){
            l1=l1.next;
            l2=l2.next.next;
        }
        return l1;
    }
    public ListNode mergeList(ListNode left,ListNode right){
        ListNode head ,relist;//结果
        if(left==null)return right;
        if(right==null)return left;
        ListNode f1=left.next,f2=right.next;
        //头结点判断
        if(left.val<right.val){
            relist=head=left;
            f2=right;
        }else{
            relist=head=right;
            f1=left;
        }
        while(f1!=null && f2 !=null){
            if(f1.val<f2.val){
                relist.next=f1;
                relist=relist.next;
                f1 = f1.next;
            }else{
                relist.next=f2;
                relist=relist.next;
                f2 = f2.next;
            }
        }
        if(f1!=null){
             relist.next=f1;
        }
        if(f2!=null){
             relist.next=f2;
        }
        return head;
    }
}


发表于 2020-08-19 19:24:14 回复(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)
ExtraLocker头像 ExtraLocker 
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)
Java
Mono_Chrome头像 Mono_Chrome 
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)
Java
放生(^o^)/~头像 放生(^o^)/~ 
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)
C/C++
hahahahaGe头像 hahahahaGe 
参考前面两位大佬写的，有一些小毛病修正了一下
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)
Java
我去个地方啊头像 我去个地方啊

题目描述

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3

Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0

Output: -1->0->3->4->5

解题思路

最近忙着追《都挺好》，差点忘记每天的任务。这一题要求时间复杂度为O(n log n) 并且用常数级别的空间复杂度。对于链表这种数据结构，不像数组那么方便，因此堆排序以及快速排序不是很方便，因此这一题用归并排序比较合适，并且对于本题，空间上不需要用数组来存储，因此是常数级别的。

代码提交

class Solution {
    //归并排序的归过程
    public ListNode sortList(ListNode head) {
        //1.判定是否为空或者只有一个元素，这也是归并排序中归的停止条件
        if(head == null || head.next == null){
            return head;
        }

        //2.将链表截成两段
        ListNode pre = null;
        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        //3.此时pre跟slow指的一样，现在将链表从中间断开
        pre.next = null;

        //4.继续再对上面分开的链表再分
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);

        //5.递归分开之后就应该按照一定的规则合并了
        return merge(l1,l2);
    }


    //归并排序的并过程
    private ListNode merge(ListNode l1,ListNode l2){
        //新建一个结点用于串联并过程结果
        ListNode tmp = new ListNode(0);
        ListNode p = tmp;

        //并的过程，谁小谁就接到p后面
        while(l1!=null && l2!=null){
            if(l1.val < l2.val){
                p.next = l1;
                l1 = l1.next;
            }else{
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }

        //如果有一段没有结束，直接接到后面即可
        if(l1 != null){
            p.next = l1;
        }

        if(l2 != null){
            p.next = l2;
        }

        //返回下一个结点
        return tmp.next;
    }
}
发表于 2019-03-22 16:24:19 回复(1)
崩溃DE够彻底︶｀头像 崩溃DE够彻底︶｀
归并排序，直接在链表上进行修改，但是实际上应该不对，因为算上函数递归栈的消耗则空间也已经到了logn级。或许堆排序才是正确答案？
public class Solution {
    public ListNode sortList(ListNode head) {
         ListNode headDown=head;
            ListNode headMiddle=head;
            ListNode headLastMiddle=head;
            int count=0;
            while(headDown!=null){
                headDown=headDown.next;
                count+=1;
               
                if(count%2==0){
                    headLastMiddle=headMiddle;
                    headMiddle=headMiddle.next;
                }
            }
            if(head==null||headMiddle==head||headMiddle==null)return head;
            ListNode headSecond=headLastMiddle.next;
            headLastMiddle.next=null;
            //get in two devided list
            head=sortList(head);
            headSecond=sortList(headSecond);
            //get them in one list
            ListNode headFirstLast=head;
            ListNode headSecondLast=headSecond;
            ListNode ***=null;
            ListNode realhead=head;
            boolean flag=false;
            while(headFirstLast!=null&&headSecondLast!=null){
                if(headFirstLast==null){
                  if(flag==false){realhead=headSecondLast;flag=true;}  
                 break;
                }
                else if(headSecondLast==null){
                     if(flag==false){realhead=headFirstLast;flag=true;}  
                     break;
                }
                else if(headFirstLast.val<=headSecondLast.val){
                    ***=headFirstLast;
                    if(flag==false){realhead=headFirstLast;flag=true;}
                    headFirstLast=headFirstLast.next;
                    if(headFirstLast!=null&&headFirstLast.val<=headSecondLast.val)continue;
                    else ***.next=headSecondLast;
                }
                else if(headFirstLast.val>headSecondLast.val){
                    ***=headSecondLast;
                    if(flag==false){realhead=headSecondLast;flag=true;}
                    headSecondLast=headSecondLast.next;
                    if(headSecondLast!=null&&headFirstLast.val>headSecondLast.val)continue;
                    ***.next=headFirstLast;
                }
               
            }
            return realhead;   
    }
   
    
}

编辑于 2019-03-22 15:23:44 回复(0)
secndf头像 secndf 
public class Solution {
    public ListNode sortList(ListNode head) {
        ListNode low = head, fast = head, pre = null, p = head;
        if (head == null || head.next == null)
            return head;
        while (fast != null && fast.next != null) {
            pre = low;
            low = low.next;
            fast = fast.next.next;
        }
        ListNode right = sortList(pre.next);
        pre.next = null;

        ListNode left = sortList(p);
        return MergeList(left, right);
    }

    public ListNode MergeList(ListNode l1, ListNode l2) {
        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;
        ListNode head = new ListNode(0), h = head, p1 = l1, p2 = l2, t;
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                t = new ListNode(p1.val);
                p1 = p1.next;
            } else {
                t = new ListNode(p2.val);
                p2 = p2.next;
            }
            h.next = t;
            h = h.next;
        }
        while (p1 != null) {
            t = new ListNode(p1.val);
            h.next = t;
            p1 = p1.next;
            h = h.next;
        }
        while (p2 != null) {
            t = new ListNode(p2.val);
            h.next = t;
            p2 = p2.next;
            h = h.next;
        }
        return head.next;
    }
}

发表于 2019-01-20 21:53:16 回复(0)
Butterfliesflyaway↘头像 Butterfliesflyaway↘
    /*
     * 思路：
     * 因为题目要求复杂度为O(nlogn),故可以考虑归并排序的思想。
     * 复杂度分析:
             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)
     *
     * 归并排序的一般步骤为：
     * 1）将待排序数组（链表）取中点并一分为二；
     * 2）递归地对左半部分进行归并排序；
     * 3）递归地对右半部分进行归并排序；
     * 4）将两个半部分进行合并（merge）,得到结果。
     */ 
public class Solution {
    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) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //以slow.next作为分割链表的中点
        ListNode head1 = head;
        ListNode head2 = slow.next;
        slow.next = null;
        //递归地对左半部分进行归并排序
        ListNode left = sortList(head1);
        //递归地对右半部分进行归并排序
        ListNode right = sortList(head2);
        //调用自定义的mergeList方法，将左右两个部分进行合并,得到结果并返回结果
        return mergeList(left, right);
    }
    
    //mergeList方法实现两个有序链表的合并
    public ListNode mergeList(ListNode head1, ListNode head2) {
        if(head1 == null) return head2;
        if(head2 == null) return head1;
        
        ListNode newHead = new ListNode(0);
        ListNode p1 = newHead;
        while(head1!=null && head2!=null) {
            if(head1.val < head2.val) {
                p1.next = head1;
                head1 = head1.next;
            }else {
                p1.next = head2;
                head2 = head2.next;
            }
            p1 = p1.next;
        }
        if(head1!=null) p1.next = head1;
        if(head2!=null) p1.next = head2;
        return newHead.next;
    }
}

发表于 2019-01-04 17:47:45 回复(0)
boom007头像 boom007
归并排序，整体装入vector中，排好再拿出来 
     void sorttest(vector<int>&p,int s,int m ,vector<int>&q) {
        if (s<m){
            int mid=(m+s)/2;
            sorttest(p,s,mid,q);
            sorttest(p,mid+1,m,q);
            int l = s;
            int f = s;
            int r = mid+1;
            while(l<=mid && r<=m){
                if(p[l]>p[r])
                    q[s++]=p[r++];
                else
                    q[s++]=p[l++];
            }
            if(l<=mid) while(l<=mid) q[s++]=p[l++];
            if(r<=m)   while(r<=m)   q[s++]=p[r++];
            while(f<=s) {p[f]=q[f];f++;}
        }
    }
    ListNode *sortList(ListNode *head) {
        if (!head || !head->next) return head;
        vector<int>p;
        ListNode *h=head;
        while(h!=NULL) { p.push_back(h->val);h=h->next;}
        vector<int>q = p;
        sorttest(p,0,p.size()-1,q);
        ListNode *f=head;
        int i = 0;
       while(f!=NULL) {f->val = p[i];f=f->next;i++;}
       return head;
    }

发表于 2018-10-07 20:45:08 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 链表 前端工程师 算法工程师 测试工程师 PHP工程师 排序 Java工程师
来自：牛客考试系统测试卷
难度：
213条回答 58526浏览

热门推荐

通过挑战的用户

查看代码

相关试题

链表排序

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号