チェーンテーブルの並べ替え問題の解決方法

チェーンテーブルを並べ替えた三大神器:1.merge(l1,l2)
l 1とl 2はそれぞれ2つの秩序化されたチェーンテーブルであり、この方法はl 1とl 2を新しい秩序化されたチェーンテーブルに結合する.

    public ListNode merge(ListNode l1,ListNode l2){
     
        ListNode dummyHead = new ListNode(0);
        ListNode head = dummyHead;
        while(l1!=null&&l2!=null){
     
            if(l1.val<l2.val){
     
                dummyHead.next = l1;
                l1 = l1.next;
                dummyHead = dummyHead.next;
            }else{
     
                dummyHead.next = l2;
                l2 = l2.next;
                dummyHead = dummyHead.next;
            }
        }
        if(l1!=null){
     
            dummyHead.next = l1;
        }
        if(l2!=null){
     
            dummyHead.next = l2;
        }
        return head.next;
    }

2.cut(head,n)この方法でチェーンテーブルheadを前のn個のノードを切り、後半のチェーンテーブルを返し、headを前のn個のノードしか残っていないチェーンテーブルに短縮する

    public ListNode cut(ListNode head,int n){
     
        while(--n!=0&&head!=null){
     
            head = head.next;
        }
        if(head!=null){
     
            ListNode right = head.next;
            head.next = null;
            return right;
        }else{
     
            return null;
        }
    }

3.dummyHeadダミーチェーンヘッダー一時的に作成されたチェーンヘッダーは、境界状況と通常の状況を統一的に処理することができます.
例題:

  O(n log n)                ，       。

   1:

  : 4->2->1->3
  : 1->2->3->4
   2:

  : -1->5->3->4->0
  : -1->0->3->4->5

コード:

class Solution {
     
    public ListNode sortList(ListNode head) {
     
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode tail = head;
        int length=0;
        while(head!=null){
     
            length++;
            head = head.next;
        }
        ListNode work;
        ListNode left;
        ListNode right;
        for(int step=1;step<length;step*=2){
     
            work = dummyHead.next;
            tail = dummyHead;
            while(work!=null){
     
                left = work;
                right = cut(left,step);
                work = cut(right,step);

                tail.next = merge(left,right);
                while(tail.next!=null){
     
                    tail = tail.next;
                }
            }
        }
        return dummyHead.next;
    }

    public ListNode cut(ListNode head,int n){
     
        while(--n!=0&&head!=null){
     
            head = head.next;
        }
        if(head!=null){
     
            ListNode right = head.next;
            head.next = null;
            return right;
        }else{
     
            return null;
        }
    }

    public ListNode merge(ListNode l1,ListNode l2){
     
        ListNode dummyHead = new ListNode(0);
        ListNode head = dummyHead;
        while(l1!=null&&l2!=null){
     
            if(l1.val<l2.val){
     
                dummyHead.next = l1;
                l1 = l1.next;
                dummyHead = dummyHead.next;
            }else{
     
                dummyHead.next = l2;
                l2 = l2.next;
                dummyHead = dummyHead.next;
            }
        }
        if(l1!=null){
     
            dummyHead.next = l1;
        }
        if(l2!=null){
     
            dummyHead.next = l2;
        }
        return head.next;
    }
}