困扰已久：单链表排序，本地测试无问题，leetcode中报错，求解原因！！！！
来源：9-2 排序链表-代码实操
慕圣9264237
2020-08-29
这个问题发过一次帖子了，随后就石沉大海了┭┮﹏┭┮
如果老师实在没时间顾忌，请求路过的同学，各路大神帮帮忙看看这个问题！！
无比感恩！！！！！
题目如下:
在我本地编辑器测试正确，但是leetcode就是无法通过！！求大神帮助！！！！！
// 单链表的快速排序法
// 声明节点
class Node {
constructor (value) {
this.val = value;
this.next = undefined;
}
}
//声明链表
class NodeList {
constructor (arr) {
let head = new Node(arr.shift());
let next = head;
arr.forEach(item => {
next.next = new Node(item);
//新生成的节点作为下一个节点的父节点
next = next.next;
})
//head为对象，this即指向对象
return head;
}
}
//交换链表两个节点的值
let swap = (p, q) => {
let val = p.val;
p.val = q.val;
q.val = val;
}
//寻找基准元素所在位置
let partion = (begin, end) => {
let val = begin.val;
let p = begin;
let q = begin.next;
while (q !== end) {
if (q.val < val) {
p = p.next;
swap(p, q);
}
q = q.next;
}
//p遍历至链表尾部时，链表头节点与p节点交换位置，让基准元素处在p节点所在位置(让基准元素跑到中间去)
swap(p, begin);
return p;
}
let sort = (begin, end) => {
if (begin !== end) {
//找基准元素
let part = partion(begin, end);
//递归-基准元素左侧节点
sort(begin, part);
//递归-基准元素右侧节点
sort(part.next, end)
}
}
var sortList = function (arr) {
let head = new NodeList(arr);
sort(head);
let res = [];
let next = head;
while (next) {
res.push(next.val);
next = next.next;
}
return res;
};
console.log(sortList([4, 2, 1, 3]));
以下是我本地运行结果:
以下是leetcode中的报错
是因为链表节点是类数组对象，无法直接使用数组方法？但是我将其转化为数组也不行。。
写回答
2回答
-
_Jack_Han_
2020-11-20
leetcode里面不用你自己生成链表，leetcode给你的参数就是链表的头节点，你只需要写排序方法即可。
10 -
qq_狼啸_0
2020-12-06
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var sortList = function(head) { // a, b 必须是传2个节点进来，而不是节点的值 function swap(a, b) { let temp = a.val a.val = b.val b.val = temp } function partition(begin, end) { // 构建快慢指针 let FP = begin.next let SP = begin while (FP !== end) { // 快指针的值小于基准值，慢指针往后移 if (FP.val < begin.val) { SP = SP.next // 如果此时快慢指针对应的值不相等，交换值 SP.val !== FP.val && swap(SP, FP) } FP = FP.next } swap(begin, SP) return SP } function sort(begin, end) { if (begin && begin !== end) { const part = partition(begin, end) sort(begin, part) sort(part.next, end) } } sort(head, null) return head };00
相似问题