Leetcode: Insertion Sort List

傷城~ 2022-08-07 11:54 63阅读 0赞

题目：Sort a linked list using insertion sort.  
即使用插入排序对链表进行排序。

思路分析：  
插入排序思想见《[排序（一）：直接插入排序 ][Link 1]》

C++参考代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution
    {
    public:
        ListNode *insertionSortList(ListNode *head)
        {
            if (!head) return nullptr;
            //previous记住当前节点的前一个节点（因为单链表进行插入操作的时候必须知道当前节点的前一个节点）
            ListNode *previous = head;
            //current节点是要往前面已经排好序的节点中进行插入的节点
            ListNode *current = head->next;
            while (current)
            {
                //small和big指针用于记录比current小和比current大的指针，small和big相邻
                ListNode *small = nullptr;
                ListNode *big = head;
                while (big->val < current->val)
                {
                    small = big;
                    big = big->next;
                }
                //如果big!=current说明current节点应该插入到small和big节点之间
                if (big != current)
                {
                    previous->next = current->next;
                    if (small) small->next = current;
                    else head = current;
                    current->next = big;
                }
                //如果big=current这时previous指向下一个节点就OK了
                else
                {
                    previous = previous->next;
                }
                //最后current节点指向previous下一个节点即current向前走一步
                current = previous->next;
            }
            return head;
        }
    };

Java参考代码：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
    public class Solution { 
        public ListNode insertionSortList(ListNode head) {
            if (head == null) return null;
            ListNode previous = head;
            ListNode current = head.next;
            while (current != null) {
                ListNode small = null;
                ListNode big = head;
                //找出介于current的big和small元素，big和small相邻
                while (big.val < current.val) {
                    small = big;
                    big = big.next;
                }
                //如果big!=current将current插入到small和big之间
                if (big != current) {
                    previous.next = current.next;
                    if (small != null) small.next = current;
                    else head = current;
                    current.next = big;
                } else {
                    previous = previous.next;
                }
                current = previous.next;
            }
            return head;
        }
    }

[Link 1]: http://blog.csdn.net/theonegis/article/details/40857481