[LeetCode] Insertion Sort List

简介: Well, life gets difficult pretty soon whenever the same operation on array is transferred to linked list.

Well, life gets difficult pretty soon whenever the same operation on array is transferred to linked list.

First, a quick recap of insertion sort:

Start from the second element (simply a[1] in array and the annoying head -> next -> val in linked list), each time when we see a node with val smaller than its previous node, we scan from the head and find the position that the current node should be inserted. Since a node may be inserted before head, we create a new_head that points to head. The insertion operation, however, is a little easier for linked list.

Now comes the code:

 1 class Solution { 
 2 public:
 3     ListNode* insertionSortList(ListNode* head) {
 4         ListNode* new_head = new ListNode(0);
 5         new_head -> next = head;
 6         ListNode* pre = new_head;
 7         ListNode* cur = head;
 8         while (cur) {
 9             if (cur -> next && cur -> next -> val < cur -> val) {
10                 while (pre -> next && pre -> next -> val < cur -> next -> val)
11                     pre = pre -> next;
12                 /* Insert cur -> next after pre.*/
13                 ListNode* temp = pre -> next;
14                 pre -> next = cur -> next;
15                 cur -> next = cur -> next -> next;
16                 pre -> next -> next = temp;
17                 /* Move pre back to new_head. */
18                 pre = new_head;
19             }
20             else cur = cur -> next;
21         }
22         ListNode* res = new_head -> next;
23         delete new_head;
24         return res;
25     }
26 };

 

目录
相关文章
|
7月前
|
Java
Leetcode 114. Flatten Binary Tree to Linked List
思路也很简单,先把root的左子树(如有)变成单链表 leftlinkedlist,把root的右子树(如有)变成单链表 rightlinkedlist,再把root的右节点变成leftlikedlist,再把rightlinkedlist接到leftlinkedlist后面,代码如下。
22 1
|
7月前
|
C++
Leetcode Copy List with Random Pointer(面试题推荐)
给大家推荐一道leetcode上的面试题,这道题的具体讲解在《剑指offer》的P149页有思路讲解,如果你手头有这本书,建议翻阅。
30 0
|
7月前
Leetcode 19.Remove Nth Node From End of List
删除单链表中的倒数第n个节点,链表中删除节点很简单,但这道题你得先知道要删除哪个节点。在我的解法中,我先采用计数的方式来确定删除第几个节点。另外我在头节点之前额外加了一个节点,这样是为了把删除头节点的特殊情况转换为一般情况,代码如下。
23 0
|
1月前
|
C++ 容器
【C++】STL容器——探究List与Vector在使用sort函数排序的区别(14)
【C++】STL容器——探究List与Vector在使用sort函数排序的区别(14)
|
1月前
|
大数据 Java 程序员
「LeetCode合集」链表(List)及经典问题
「LeetCode合集」链表(List)及经典问题
34 0
|
11月前
|
算法 C++
SGI-STL源码剖析之list::sort()
SGI-STL源码剖析之list::sort()
83 0
LeetCode 75 Sort Colors 颜色分类(荷兰国旗)
Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
73 0
LeetCode 141. 环形链表 Linked List Cycle
LeetCode 141. 环形链表 Linked List Cycle
|
1天前
|
Java API
使用 Java 来实现两个 List 的差集操作
使用 Java 来实现两个 List 的差集操作
9 3
|
3天前
|
Java 索引
Java List实战:手把手教你玩转ArrayList和LinkedList
【6月更文挑战第17天】在Java中,ArrayList和LinkedList是List接口的实现,分别基于动态数组和双向链表。ArrayList适合索引访问,提供快速读取,而LinkedList擅长插入和删除操作。通过示例展示了两者的基本用法,如添加、访问、修改和删除元素。根据场景选择合适的实现能优化性能。