leetcode.147. 对链表进行插入排序

Love The Way You Lie 2022-12-22 11:21 95阅读 0赞

# 147. 对链表进行插入排序 #

对链表进行插入排序。

![在这里插入图片描述][9400029b6559a5f16c48610324ceb961.png_pic_center]

## c++版插入排序 ##

别上面的图误导了，**数组的插入排序和链表的是不一样的**。  
如果是数组的插入排序，则数组的前面部分是有序序列，每次找到有序序列后面的第一个元素（待插入元素）的插入位置，将有序序列中的插入位置后面的元素都往后移动一位，然后将待插入元素置于插入位置。

对于链表而言，插入元素时只要更新相邻节点的指针即可，不需要像数组一样将插入位置后面的元素往后移动，因此插入操作的时间复杂度是 O(1)，但是找到插入位置需要遍历链表中的节点，时间复杂度是 O(n)，因此链表插入排序的总时间复杂度仍然是 O(n^2)，其中 n 是链表的长度。  
[官方题解步骤][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2U4OTEzNzc_size_16_color_FFFFFF_t_70_pic_center]  
排序前`-1->5->3->4->0`，排序后`-1->0->3->4->5`。  
代码如下：

class Solution { 
    public:
        ListNode* insertionSortList(ListNode* head) { 
        	//1.首先判断给定的链表是否为空，若为空，则不需要进行排序，直接返回。
            if (head == nullptr) { 
                return head;
            }
            //2.创建哑节点 dummyHead，令 dummyHead.next = head。引入哑节点是为了便于在 head 节点之前插入节点。
            ListNode* dummyHead = new ListNode(0);
            dummyHead->next = head;
            //3.维护 lastSorted 为链表的已排序部分的最后一个节点，初始时 lastSorted = head。
            ListNode* lastSorted = head;
            //4.维护 curr 为待插入的元素，初始时 curr = head.next。
            ListNode* curr = head->next;
            
            while (curr != nullptr) { 
            	//5.比较 lastSorted 和 curr 的节点值。
            	//若 lastSorted.val <= curr.val，说明 curr 应该位于 lastSorted 之后，
            	//将 lastSorted 后移一位，curr 变成新的 lastSorted。
                if (lastSorted->val <= curr->val) { 
                    lastSorted = lastSorted->next;
                } else { 
                	//否则，从链表的头节点开始往后遍历链表中的节点，寻找插入 curr 的位置。令 prev 为插入 curr 的位置的前一个节点，
                    ListNode *prev = dummyHead;
                    while (prev->next->val <= curr->val) { 
                        prev = prev->next;
                    }
                    //进行如下操作，完成对 curr 的插入
                    lastSorted->next = curr->next;
                    curr->next = prev->next;
                    prev->next = curr;
                }
                
    			//6.令 curr = lastSorted.next，此时 curr 为下一个待插入的元素。
    			//7.重复第 5 步和第 6 步，直到 curr 变成空，排序结束。
    			//8.返回 dummyHead.next，为排序后的链表的头节点。
    
                curr = lastSorted->next;
            }
            return dummyHead->next;
        }
    };

ListNode 对象

public class ListNode { 
          int val;
          ListNode next;
          ListNode(int x) {  val = x; }
      }

## java版插入排序 ##

class Solution { 
        public ListNode insertionSortList(ListNode head) { 
            // 1. 首先判断给定的链表是否为空，若为空，则不需要进行排序，直接返回。
            if(head == null){ 
                return head;
            }
    
            // 2. 链表初始化操作
            ListNode dummyHead = new ListNode(0); // 引入哑节点
            dummyHead.next = head;                // 目的是在head之前插入节点
            ListNode lastSorted = head;           // 维护lastSorted为链表已经排好序的最后一个节点并初始化
            ListNode curr = head.next;            // 维护curr 为待插入的元素并初始化
    
            // 3. 插入排序
            while(curr != null){ 
                if(lastSorted.val <= curr.val){      // 说明curr应该位于lastSorted之后
                    lastSorted = lastSorted.next;   // 将lastSorted后移以为,curr变成新城lastSorted
                }else{                               // 否则,从链表头结点开始向后遍历链表中的节点
                    ListNode prev = dummyHead;      // 从链表头开始遍历 prev是插入节点curr位置的前一个节点
                    while(prev.next.val <= curr.val){  // 循环退出的条件是找到curr应该插入的位置
                        prev = prev.next;
                    }
                    // 以下三行是为了完成对curr的插入
                    lastSorted.next = curr.next;
                    curr.next = prev.next;
                    prev.next = curr;
                }
                curr = lastSorted.next; // 此时 curr 为下一个待插入的元素
            }
            // 返回排好序的链表
            return dummyHead.next;
        }
    }

有些鞋同这三行代码对不太理解

lastSorted.next = curr.next;
              curr.next = prev.next;
              prev.next = curr;

可以看看[单链表按顺序插入节点][Link 2]。

[9400029b6559a5f16c48610324ceb961.png_pic_center]: /images/20221120/b1e8edb2907d4b9bbac35f9b5cbcaeed.png
[Link 1]: https://leetcode-cn.com/problems/insertion-sort-list/solution/dui-lian-biao-jin-xing-cha-ru-pai-xu-by-leetcode-s/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2U4OTEzNzc_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/7c53f641a8024f2f9ab5b3097c23d21c.png
[Link 2]: https://blog.csdn.net/e891377/article/details/97122344