【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){
                
                // 子链1
                ListNode head1 = cur;
                for(int i = 1 ; i < subLen && cur.next !=null ; i++){
                    cur = cur.next;
                }

                // 子链2
                ListNode 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;
                }

                // 记录next
                ListNode 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;
        }
    }
}