在O(n log n)的时间内使用常数级空间复杂度对链表进行排序。
[编程题]链表排序
// 单链表的快速排序 时间复杂度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)
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)
利用归并排序；依次递归：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题解的递归+归并解法，空间复杂度不能满足要求。
官方题解可以参考一下：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)
题目描述
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)
归并排序，直接在链表上进行修改，但是实际上应该不对，因为算上函数递归栈的消耗则空间也已经到了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;
}
}
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)
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)
/*
* 思路：
* 因为题目要求复杂度为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）,得到结果。
* 思路：
* 因为题目要求复杂度为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)
问题信息
通过挑战的用户
查看代码-
2023-03-08 00:10:27 -
2023-03-04 01:22:51
-
2023-01-05 17:02:41
-
2022-11-30 15:29:41
-
2022-10-18 11:56:20
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
