LeetCode排序链表C++解法(详解)

简介: 给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表

给你链表的头结点 head ,请将其按升序排列并返回排序后的链表

示例 1:

image.png

输入:head = [4,2,1,3]

输出:[1,2,3,4]

image.png

输入:head = [-1,5,3,4,0]

输出:[-1,0,3,4,5]


示例 3:

输入:head = []

输出:[]


三个步骤

1)取出链表里面的元素放到数组里面

这里面通过遍历链表,将所有值放到这个数组里面。

ListNode *p = head; 
while(p)
        {
            num.push_back(p->val);
            p = p ->next;
        }

2)利用sort函数讲其排序

sort(num.begin(),num.end());

3)在通过遍历将数组里面的值依次放到链表中

ListNode *q = head;  
for(auto it =num.begin();it!=num.end();it++)
        {
            q->val = *it;
            q = q->next;
        }
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        vector<int> num;
        ListNode *p = head;
        ListNode *q = head;
        while(p)
        {
            num.push_back(p->val);
            p = p ->next;
        }
        sort(num.begin(),num.end());
        for(auto it =num.begin();it!=num.end();it++)
        {
            q->val = *it;
            q = q->next;
        }
        return head;
    }
}

注:

这里面自己写的时候有个bug,就是 q->val =*it 和  q = q->next 的位置调换,导致会出现q在最后指向的时候出现指向为空的情况 。我以为链表的头结点不存值,所以没有先让头结点next了一下

相关文章
|
18小时前
|
Java Python
二刷力扣--链表
二刷力扣--链表
|
1天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
1天前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
1天前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
1天前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
|
5天前
|
存储 算法 搜索推荐
深入解析力扣179题:最大数(自定义排序法详解及模拟面试问答)
深入解析力扣179题:最大数(自定义排序法详解及模拟面试问答)
|
5天前
|
存储 算法 数据可视化
【模拟面试问答】深入解析力扣164题:最大间距(桶排序与排序方法详解)
【模拟面试问答】深入解析力扣164题:最大间距(桶排序与排序方法详解)
|
5天前
|
存储 算法 数据可视化
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
|
5天前
|
存储 算法 数据可视化
深入解析力扣157题:用Read4高效读取N个字符(多种解法与详细图解)
深入解析力扣157题:用Read4高效读取N个字符(多种解法与详细图解)
|
5天前
|
存储 算法 数据可视化
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)
力扣156题最全解法:如何上下翻转二叉树(递归与迭代方法详解,附图解)