【CT】LeetCode手撕—148. 排序链表

题目

• 原题连接：148. 排序链表

1- 思路

• 排序链表，将每个元素看做一个单独的链表 ——> 归并排序 ——> 每次将单独的链表合并

2- 实现

⭐148. 排序链表——题解思路

class Solution {public ListNode sortList(ListNode head) {// 1. 先求链表长度int len = 0;ListNode forH = head;while(forH!=null){len++;forH = forH.next;}ListNode dummyHead = new ListNode(-1);dummyHead.next = head;// 2. 利用 for 拆分for(int subLen = 1 ; subLen < len;subLen*=2){ListNode prev = dummyHead, cur = dummyHead.next;while(cur!=null){// 子链1ListNode head1 = cur;for(int i = 1 ; i < subLen && cur.next !=null ; i++){cur = cur.next;}// 子链2ListNode head2 = cur.next;cur.next = null;cur = head2;for(int i = 1 ; i < subLen && cur!=null && cur.next !=null ;i++){cur = cur.next;}ListNode next = null;if(cur!=null){next = cur.next;cur.next = null;}ListNode merged = mergeList(head1,head2);prev.next = merged;while(prev.next!=null){prev = prev.next;}cur = next;}}return dummyHead.next;}public ListNode mergeList(ListNode head1,ListNode head2){ListNode dummyHead = new ListNode(0);ListNode cur = dummyHead;ListNode forA = head1;ListNode forB = head2;while(forA!=null && forB !=null){if(forA.val < forB.val){cur.next = forA;forA = forA.next;}else{cur.next = forB;forB = forB.next;}cur = cur.next;}if(forA!=null){cur.next = forA;}else{cur.next = forB;}return dummyHead.next;}
}

3- ACM 实现

public class sortLink {static class ListNode{int val;ListNode next;ListNode(){}ListNode(int x){val = x;}}// 合并链表public static ListNode sortList(ListNode head){// 1. 求长度int len = 0;ListNode l = head;while (l!=null){len++;l = l.next;}ListNode dummyHead = new ListNode(-1);dummyHead.next = head;// 自底向上for(int subLen = 1 ; subLen < len;subLen*=2){ListNode prev = dummyHead,cur = dummyHead.next;while(cur!=null){ListNode head1 = cur;for(int i = 1; i < subLen && cur.next!=null; i++){cur = cur.next;}ListNode head2 = cur.next;cur.next = null;cur = head2;for(int i = 1; i < subLen && cur!=null && cur.next!=null ; i++){cur = cur.next;}// 记录nextListNode next = null;if(cur!=null){next = cur.next;cur.next = null;}ListNode merged = merged(head1,head2);prev.next = merged;while(prev.next!=null){prev = prev.next;}cur = next;}}return dummyHead.next;}public static ListNode merged(ListNode head1, ListNode head2){ListNode dummyHead = new ListNode(-1);ListNode cur = dummyHead;while(head1!=null && head2 !=null){if(head1.val<head2.val){cur.next = head1;head1 = head1.next;}else{cur.next = head2;head2 = head2.next;}cur = cur.next;}if(head1!=null){cur.next = head1;}else{cur.next = head2;}return dummyHead.next;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入链长度");int n = sc.nextInt();System.out.println("输入链表元素");ListNode head=null,tail=null;for(int i = 0 ; i < n;i++){ListNode newNode = new ListNode(sc.nextInt());if(head==null){head = newNode;tail = newNode;}else{tail.next = newNode;tail = tail.next;}}ListNode res = sortList(head);System.out.println("排序后的链表是");while(res!=null){System.out.print(res.val +" ");res = res.next;}}
}