package com.mxnet;
public class Solution148 {
public static void main(String[] args) {
}
/**
* 给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
* @param head
* @return
* 思路:
* 1. 使用归并排序的思路,即依次二分链表再合并
* 2. 递归的将链表二分,递归结束的条件为子链表只剩下一个元素或者子链表为空
* 3. 对于而二分的子链表,使用链表的从小到达排序算法将其合并
* 4. 最后则得到完整升序的链表
*/
public ListNode sortList(ListNode head) {
return sortList(head,null);
}
/**
* 递归将一条链表进行排序
* @param head
* @param tail
* @return
*/
public ListNode sortList(ListNode head, ListNode tail) {
//递归结束条件:链表中没有元素或者只有一个元素
if (head == null){
return head;
}
if (head.next == tail){
head.next = null;
return head;
}
//创建快慢指针
ListNode fast = head;
ListNode slow = head;
//快指针移动一次,慢指针移动两次,当快指针到达链表末尾时,慢指针刚好到链表中间
while (fast != tail){
fast = fast.next;
slow = slow.next;
if (fast != tail){
fast = fast.next;
}
}
ListNode mid = slow;
//递归排序并组合
ListNode list1 = sortList(head, mid);
ListNode list2 = sortList(mid, tail);
ListNode merge = merge(list1, list2);
return merge;
}
/**
* 将两条链表由小到大合并
* @param head1 链表1
* @param head2 链表2
* @return
* 思路:
* 1. 创建一条新链表用于保存排好序的链表
* 2. 循环将两条链表最前边的值进行比较,每次取出最小的挂在到新链表上
* 3. 若两条链表长度不一致,则在循环结束后将较长链表后半部分挂在新链表后边
*/
public ListNode merge(ListNode head1, ListNode head2){
//创建新链表保存排好序的链表
ListNode dummyHead = new ListNode();
//创建辅助链表
ListNode temp = dummyHead;
ListNode temp1 = head1;
ListNode temp2 = head2;
//每次通过节点大小取出一个节点链接到新链表后面
while (temp1 != null && temp2 != null){
if (temp1.val <= temp2.val){
temp.next = temp1;
temp1 = temp1.next;
}else if (temp1.val > temp2.val){
temp.next = temp2;
temp2 = temp2.next;
}
//temp辅助指针后移
temp = temp.next;
}
//当其中一条链表为空,另一条不为空时,将不为空链表连接到后面
if (temp1 != null){
temp.next = temp1;
}else if (temp2 != null){
temp.next = temp2;
}
return dummyHead.next;
}
}
标签:head,ListNode,leetcode148,next,链表,temp2,return,排序
From: https://www.cnblogs.com/mx-info/p/16625298.html