LeetCode147 Insertion Sort List

LeetCode 147 Insertion Sort List

遇到操作linked list的题目,先判断head或者head.next是否为空。
之后再对node数>=2的情况进行讨论。

首先回忆一下insertion sort!!!
搜索数组,如果当前的数curr小于前一个数prev,则将该数curr插入到head到prev之间的位置。

代码:

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = head, curr = head.next;
        
        while (curr != null) {
            if (curr.val >= prev.val) {
                prev = curr;
                curr = curr.next;
            } else {
                // Start from dummy and head, to find where to insert the curr node
                // Find the first node c whose val is >= curr, insert curr node before node c
                ListNode next = curr.next, p = dummy, c = dummy.next;
                while (c.val < curr.val) {
                    p = p.next;
                    c = c.next;
                }
                p.next = curr;
                curr.next = c;
                curr = next;
                prev.next = curr;
            }
        }
        
        return dummy.next;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容