淄博学校网站建设方案,北京营销型网站,闸北区网站设计与制,线上代运营公司前言
链表的归并排序和数组的归并排序类似#xff0c;只是在操作原有操作数组的基础上对链表进行操作。喜欢的可以试试吧。
实现原理
链表归并排序是一种常见的排序算法#xff0c;它利用了归并排序的思想来对链表进行排序。与数组不同#xff0c;链表在归并排序中的主要…前言
链表的归并排序和数组的归并排序类似只是在操作原有操作数组的基础上对链表进行操作。喜欢的可以试试吧。
实现原理
链表归并排序是一种常见的排序算法它利用了归并排序的思想来对链表进行排序。与数组不同链表在归并排序中的主要挑战是如何将链表分割为两个子链表以及如何合并两个有序的子链表。
下面是链表归并排序的一般步骤 分割阶段找到链表的中点将链表分成两个子链表。可以使用快慢指针技巧来找到中点。 递归排序对两个子链表分别进行递归排序直到子链表长度为1或0。 合并阶段将两个有序的子链表合并成一个有序的链表。可以使用迭代或递归来实现合并操作。
具体代码实现
class ListNode {int val;ListNode next;ListNode(int val) {this.val val;}
}public class MergeSortLinkedList {public ListNode mergeSort(ListNode head) {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 mid slow.next;slow.next null;ListNode left mergeSort(head);ListNode right mergeSort(mid);return merge(left, right);}private ListNode merge(ListNode left, ListNode right) {ListNode dummy new ListNode(0);ListNode current dummy;while (left ! null right ! null) {if (left.val right.val) {current.next left;left left.next;} else {current.next right;right right.next;}current current.next;}if (left ! null) {current.next left;}if (right ! null) {current.next right;}return dummy.next;}public static void printList(ListNode head) {ListNode current head;while (current ! null) {System.out.print(current.val - );current current.next;}System.out.println(null);}public static void main(String[] args) {MergeSortLinkedList sorter new MergeSortLinkedList();// 创建链表ListNode head new ListNode(4);head.next new ListNode(2);head.next.next new ListNode(1);head.next.next.next new ListNode(3);// 打印原始链表System.out.println(Original List:);printList(head);// 对链表进行归并排序ListNode sortedHead sorter.mergeSort(head);// 打印排序后的链表System.out.println(\nSorted List:);printList(sortedHead);}
}QA:待定
