从归并排序引申到排序链表-图解

本文主要是介绍从归并排序引申到排序链表-图解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

从归并排序引申到排序链表

归并排序

递归版

    //合并排序public static void mergeSort(int[] nums) {mergeSortHelper(0, nums.length, nums); //没有-1}private static void mergeSortHelper(int low, int high, int[] nums) {if (low >= high || high - low == 1) { //区间为空区间或只有一个元素，不用排序return;}int mid = (low+high)/2;//递归对子区间归并排序mergeSortHelper(low, mid, nums);//[low, mid)mergeSortHelper(mid, high, nums);//[mid, high)merge(low, mid, high, nums);}//合并两个有序数组private static void merge(int low, int mid, int high, int[] nums) {int i = low;int j = mid;int t = high - low;int[] extra = new int[t];int k = 0;while (i < mid && j < high) {//保证稳定性if (nums[i] <= nums[j]) {extra[k++] = nums[i++];} else {extra[k++] = nums[j++];}}while (i < mid) {extra[k++] = nums[i++];}while (j < high) {extra[k++] = nums[j++];}for (int x = 0; x < t; x++) {nums[low+x] = extra[x];}}

非递归版

    //非递归版本public static void mergeSort2(int[] nums) {//1.将数组拆分为若干个长度为size的子数组for (int size = 1; size < nums.length; size *= 2) {//1.1循环，开始对子数组操作for (int i = 0; i < nums.length; i += 2*size) {//1.1.1得到子数组n1int n1 = i;//1.1.2得到子数组n2int n2 = i+size;if (n2 > nums.length) {continue;}//1.1.3去掉n1 n2的内容之后原数组剩余的内容用next保存int next = n2 + size;if (next > nums.length) {next = nums.length;}merge(nums, n1, n2, next);}}}

排序链表

OJ链接

递归版

public class $148 {//法一：使用递归，自顶向下归并排序public ListNode sortList(ListNode head) {return sortList(head, null);}private ListNode sortList(ListNode head, ListNode tail) {//链表为空if (head == null) {return head;}//链表只有一个节点if (head.next == tail) {head.next = null;return head;}//1.找到链表的中间节点（返回第二个中间节点）ListNode fast = head;ListNode slow = head;while (fast != tail && fast.next != tail) { //tailfast = fast.next.next;slow = slow.next;}//2.对两个子链表分别排序ListNode mid = slow;ListNode list1 = sortList(head, mid);ListNode list2 = sortList(mid, tail);//3.合并两个已排序子链表ListNode sorted = merge(list1, list2);return sorted;}private ListNode merge(ListNode list1, ListNode list2) {ListNode mergedHead = new ListNode(0);ListNode temp = mergedHead;ListNode temp1 = list1;ListNode temp2 = list2;while (temp1 != null && temp2 != null) {if (temp1.val < temp2.val) {temp.next = temp1;temp1 = temp1.next;} else {temp.next = temp2;temp2 = temp2.next;}temp = temp.next;}if (temp1 != null) {temp.next = temp1;} else {temp.next = temp2;}return mergedHead.next;}
}

非递归版

public class $148 {//法二：自底向上归并排序public ListNode sortList2(ListNode head) {//1.得到链表长度int len = 0;ListNode node = head;while (node != null) {node = node.next;len++;}//2.引入虚拟头结点，连接headListNode dummyHead = new ListNode(-1);dummyHead.next = head;//3将链表拆分为若干个长度为size的子链表for (int size = 1; size < len; size *= 2) {//3.1prev，curListNode prev = dummyHead;ListNode cur = dummyHead.next;//3.2循环，开始对子链表进行操作while (cur != null) {//3.2.1得到长度为size的链表l1ListNode l1 = cur;for (int i = 1; i < size && cur.next != null; i++) {cur = cur.next;}//3.2.2得到长度为size的链表l2，并切断两个链表的连接ListNode l2 = cur.next;cur.next = null;cur = l2;for (int i = 1; i < size && cur != null && cur.next != null; i++) {cur = cur.next;}//3.2.3去掉链表1链表2之后原链表剩余的内容用next保存//同时切断next与两个链表的连接ListNode next = null;if (cur != null) {next = cur.next;cur.next = null;}//3.2.4合并两个排序链表得到mergedListNode merged = merge(l1, l2);//3.2.5prev连上merged，将prev指向merged的末尾prev.next = merged;while (prev.next != null) {prev = prev.next;}//3.2.6cur指向nextcur = next;}}return dummyHead.next;}private ListNode merge(ListNode list1, ListNode list2) {ListNode mergedHead = new ListNode(0);ListNode temp = mergedHead;ListNode temp1 = list1;ListNode temp2 = list2;while (temp1 != null && temp2 != null) {if (temp1.val < temp2.val) {temp.next = temp1;temp1 = temp1.next;} else {temp.next = temp2;temp2 = temp2.next;}temp = temp.next;}if (temp1 != null) {temp.next = temp1;} else {temp.next = temp2;}return mergedHead.next;}
}

这篇关于从归并排序引申到排序链表-图解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---