对链表进行插入排序

2020-11-20

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
 

示例 1：

输入: 4->2->1->3
输出: 1->2->3->4
示例 2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5
通过次数61,061提交次数91,279

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insertion-sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

又一次被链表的复杂关系搞晕了

用了不太合题意的辅助空间做出来的

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (null == head) {
            return head;
        }

        ListNode node = new ListNode(0);
        node.next = new ListNode(head.val);

        ListNode tempNode = node.next;
        head = head.next;

        while (head != null) {
            if (head.val > tempNode.val) {
                tempNode.next = new ListNode(head.val);
                tempNode = tempNode.next;
            } else {
                ListNode sortedNode = node;
                ListNode replace = new ListNode(head.val);
                replace.next = null;
                boolean flag = false;
                while (sortedNode != null && sortedNode.next != null) {
                    if (sortedNode.next.val < head.val) {
                        sortedNode = sortedNode.next;
                    } else {
                        ListNode curNext = sortedNode.next;
                        sortedNode.next = replace;
                        sortedNode.next.next = curNext;
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    sortedNode.next = replace;
                }
            }

            head = head.next;

        }

        return node.next;
    }
}

借用官方的图理清思路：
avatar

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummyHead = new ListNode(0);
        // dummyHead是拍好序列的链表
        // 从原先链表中选择一个元素时，首先与dummyHead的第一个元素比较，如果大于该元素，就往后移动，直至到达不大于的位置，断开链表将值插入，然后合并链表
        dummyHead.next = head;
        ListNode lastSorted = head, curr = head.next;
        while (curr != null) {
            if (lastSorted.val <= curr.val) {
                lastSorted = lastSorted.next;
            } else {
                ListNode prev = dummyHead;
                // 定位到排好序的部分的第一个位置
                while (prev.next.val <= curr.val) {
                    // 如果某个元素小于当前的值，后移指针直至不小于的位置
                    prev = prev.next;
                }
                // 将cur节点从链表中断开
                lastSorted.next = curr.next;
                // 将cur节点插入有序的链表
                curr.next = prev.next;
                prev.next = curr;
            }
            curr = lastSorted.next;
        }
        return dummyHead.next;
    }
}

参考文献

官方题解LeetCode-Solution

jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true