菜鸡刷Leetcode之148. Sort List Medium

发布时间:2019-06-23 22:00:10发布者:Mr.Zhang阅读(186)

https://leetcode.com/problems/sort-list/

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

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

由于水平有限,初期不会放自己写的代码,防止误人子弟。主要是对Leetcode的Discussion中的高赞方法(之一)进行解读,而解读方式主要是为它们添加合适的注释。之所以这么做,一是因为leetcode中的discussion很多上来就是一顿代码,菜鸡的我往往接受不了;另一方面,很多博客都是前面写解释,然后最后放上一顿代码,菜鸡的我还是接受不了。这些原因导致我看别人的思路和代码感觉很慢,另一方面英文初次理解起来确实比较麻烦,所以一气之下,我打算写个我认为理想的方式——为别人的代码添加注释,希望能帮助到你。(今天看新闻,柯南动画已经更新到999了!!!)

下面代码参考连接:

https://leetcode.com/problems/sort-list/discuss/46712/Bottom-to-up(not-recurring)-with-o(1)-space-complextity-and-o(nlgn)-time-complextity

/**
 * Merge sort use bottom-up policy, 
 * so Space Complexity is O(1)
 * Time Complexity is O(NlgN)
 * stable sort
*/
/*
* 解决该题需要使用归并排序,而这里的归并排序需要使用自底向上策略;
这样才能实现,空间复杂度O(1),时间复杂度O(NlgN)
*/
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if(!head || !(head->next)) return head;  // 判断传入的链表头结点是否为空或者链表是否只有一个元素
        
        //get the linked list's length
        // 下面代码将得到链表的长度
        ListNode* cur = head;
        int length = 0;
        while(cur){
            length++;
            cur = cur->next;
        }
        
        //设定一个虚节点,并指向头结点,方便后续操作
        ListNode dummy(0);  // 我不太喜欢这么创建结点的方式,更喜欢如:ListNode* dummy = new ListNode(0)
        dummy.next = head;
        // 创建三个节点指针:left用来存放切分后第一部分链表的头结点,right用来存放第二部分的头结点,tail用来存放归并之后的有序链表的尾节点(方便下面的拼接)
        ListNode *left, *right, *tail;
        for(int step = 1; step < length; step <<= 1){  // 左移代表乘以2
            // 初次遍历的时候,由于dummy.next等于头指针,所以cur初次的值是头指针;但是cur主要用来存放什么呢?
            // 从下面的while循环可以看出端倪:每次都是以步长step为基准,对链表进行切分(split(left, step)),
            // 使链表分为两部分,前面的一部分包含step个元素;后面是剩下的链表(len - step个元素),
            // 对后面这个链表同理,也做了一次切分(split(right, step)),此时的最后一部分链表的头指针由cur来存放
            // 简单一句话:每一次while循环都需要切两次,而cur用来存放最后一次切分的剩下的链表的头结点。
            // 而剩下这部分链表是没有排序和归并的(还是杂乱无章)
            // 此外,值得注意的是while循环在for循环里,也就是每一个step,链表都会遍历的执行,实现step内的元素有序
            // while循环将链表变成一段一段有序的了(step长度为一段)
            cur = dummy.next;
            tail = &dummy;
            while(cur){
                left = cur;
                right = split(left, step);
                cur = split(right,step);
                tail = merge(left, right, tail);
            }
        }
        return dummy.next;
    }
private:
    /**
     * Divide the linked list into two lists,
     * while the first list contains first n ndoes
     * return the second list's head
     */
    /*
    * split函数将链表分成两部分链表,
    * 第一部分链表分包含n个节点,函数最后返回第二部分链表的头结点
    */
    ListNode* split(ListNode *head, int n){
        //if(!head) return NULL;
        // 遍历到第n个节点,后面就可以实现将第n个节点和第n+1个节点断开
        for(int i = 1; head && i < n; i++) head = head->next;  
        
        if(!head) return NULL;
        // 下面两行实现断开这个操作
        ListNode *second = head->next;
        head->next = NULL;
        return second;
    }
    /**
      * merge the two sorted linked list l1 and l2,
      * then append the merged sorted linked list to the node head
      * return the tail of the merged sorted linked list
     */
    /*
    * 将两个排好序的链表l1和l2进行合并
    * 然后将合并好的新链表连接到传入的head节点之后
    * 最后返回归并排序好后的有序链表的尾节点
    */
    ListNode* merge(ListNode* l1, ListNode* l2, ListNode* head){
        ListNode *cur = head;  // 这里的cur相当于下面一步步合并出来的有序链表的尾结点,去连接下一个该存放的节点,并更新
        while(l1 && l2){
            if(l1->val > l2->val){
                cur->next = l2;
                cur = l2;
                l2 = l2->next;
            }
            else{
                cur->next = l1;
                cur = l1;
                l1 = l1->next;
            }
        }
        cur->next = (l1 ? l1 : l2);  // 将还有元素的部分链表连接到后面
        while(cur->next) cur = cur->next;  // 得到尾结点
        return cur;
    }
};

第一次写博客,在注释中啰嗦了这么多,才明白为什么大部分人不喜欢在代码中通过注释把事情说明白,因为太难了!

即使写了这么多,我依然觉得读者可能需要在理解代码的基础上才能看得懂注释,所以,理解代码没有捷径,就是干!

当然,代码中注释的使命是为了简单提醒,做到简洁明了是最好的风格。这里写这么多废话主要是为了更快理解这个人写的代码,希望这个目的达成了!





本文转自博客园,原文地址:https://www.cnblogs.com/Flash-ylf/p/11001031.html