当前位置：首页 > article >正文

算法6（力扣148）-排序链表

article 2025/1/21 16:35:59

1、问题

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

2、采用例子

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

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

3、实现思路

将链表拆分成节点，存入数组使用sort排序，再用reduce重建链接

4、具体步骤

（1）定义链表结构

（2）定义头结点

（3）进入函数

1）空链表直接返回

2）创建空数组，当前节点

3）进入循环

4）将当前节点加入数组

5）使用临时变量存取当前节点的下一节点，方便后续断开其余节点不丢失

6）断开当前节点（让当前节点的指针指向空即可）

7）将临时变量的值赋给当前节点，进行下一轮循环

（4）函数结束后，得到各节点（节点中其实包含有其后续节点，不过不影响），进行sort排序（通过节点的val值比较即可），排序后各节点的next指针为空，通过reduce建立联系，然后返回数组中的一个即可

（5）调用函数，可查看链表是否正确

5、完整代码

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>排序链表</title>
</head>
<body>
    <p>
        给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
    </p>
    <p>
        输入：head = [4,2,1,3]
        输出：[1,2,3,4]
    </p>
    <script>
        class ListNode{
            constructor(val, next){
                this.val = val
                this.next = next
            }
        }
        let head = new ListNode(4,new ListNode(2,new ListNode(3,new ListNode(1))))
        // console.log(head);
        sortList(head)
       function sortList(head){
        // 空链表
        if(!head)return head;
        // 创建数组
        let arr = []
        // 当前节点
        let cur = head
        // 将链表拆分为数组
        // 遍历链表
        while (cur) {
            // 将当前节点加入链表
            arr.push(cur)
            // 将链表后面的节点存入临时变量，方便后面断开节点
            let tmp = cur.next
            // 断开链表节点，方便使用sort排序
            cur.next = null
            // 链表指针后移，便于添加下一节点
            cur = tmp
        }
        // console.log(arr);
        // 使用sort排序得到没有联系的有序节点数组，使用reduce添加链表联系
        // p是前一个值,v当前值
        arr.sort((a,b)=> a.val-b.val).reduce((p, v) =>  p.next = v
        )
        //  console.log(arr);
        return arr[0]
        }
       
        
        
    </script>
</body>
</html>

6、力扣通过代码

var sortList = function(head) {
     if(!head)return head;
        // 创建数组
        let arr = []
        // 将链表拆分为数组
        let cur = head
        // 遍历链表
        while (cur) {
            // 将当前节点加入链表
            arr.push(cur)
            // 将链表后面的节点存入临时变量，方便后面断开节点
            let tmp = cur.next
            // 断开链表节点，方便使用sort排序
            cur.next = null
            // 链表指针后移，便于添加下一节点
            cur = tmp
        }
        // console.log(arr);
        // 使用sort排序得到没有联系的有序节点数组，使用reduce添加链表联系
        // p是前一个值,v当前值
        arr.sort((a,b)=> a.val-b.val).reduce((p, v) =>  p.next = v
        )
        //  console.log(arr);
        return arr[0]
};

查看全文

http://www.kler.cn/a/512315.html