==========================努力奋斗财源广进==========================

一、算法题目

给定一个节点数为n的无序单链表，对其按升序排序。

二、题解

1、我的题解

import java.util.*;
public class Solution {
    //合并两段有序链表
    ListNode merge(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null){
            return pHead2;
        }
        if(pHead2 == null){
            return pHead1;
        }
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while(pHead1 != null && pHead2 != null){
            if(pHead1.val > pHead2.val){
                cur.next = pHead2;
                pHead2 = pHead2.next;
            } else{
                cur.next = pHead1;
                pHead1 = pHead1.next;
            }
            cur = cur.next;
        }
        if(pHead1 != null){
            cur.next = pHead1;
        }
        if(pHead2 != null){
            cur.next = pHead2;
        }
        return head.next;      
    }
    
    public ListNode sortInList (ListNode head) {
        //递归的思想，一定确认好
        //递归的思路应该是终止条件
        if(head == null || head.next == null){
            return head;
        }
        //找到链表的中心，需要三个指针。
        ListNode left = head;
        ListNode mid = head.next;
        ListNode right = head.next.next;
        while(right != null && right.next != null){
            left = left.next;
            mid = mid.next;
            right = right.next.next;
        }
        //找到中点之后，要把链表进行断开
        left.next = null;
        return merge(sortInList(head),sortInList(mid));
    }
}

2、优秀题解

//待定

三、解法心得

这道题虽然题目简单，但是动手开始做，对于链表还是比较难。

题解法，代码比较长，但是总结来看，使用到了递归方法和合并两个有序链表的方法。

递归方法里面使用到了快慢指针，为了能切分指针也使用到了切割方法，就是快指针是满指针的两倍。第三个指针在慢指针的前一个，用于切分链表的指针。

就是将链条不断的切分，切分成最小单位，最小单位为一个或者零个节点，然后对这么多单位进行有序合并。

四、自我监督

评论区记录复习记录