Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

148. 排序链表 #53

Open
webVueBlog opened this issue Sep 5, 2022 · 0 comments
Open

148. 排序链表 #53

webVueBlog opened this issue Sep 5, 2022 · 0 comments

Comments

@webVueBlog
Copy link
Owner

148. 排序链表

Description

Difficulty: 中等

Related Topics: 链表, 双指针, 分治, 排序, 归并排序

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

示例 1:

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

示例 2:

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

示例 3:

输入:head = []
输出:[]

提示:

  • 链表中节点的数目在范围 [0, 5 * 104] 内
  • -105 <= Node.val <= 105

**进阶:**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?

Solution

Language: JavaScript

/**
 * 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) {
    if (head === null || head.next === null) {
        return head
    }

    let midNode = getMiddleNode(head)
    let rightHead = midNode.next
    midNode.next = null

    let left = sortList(head)
    let right = sortList(rightHead)

    return mergeTwoLists(left, right)
};

// 利用快慢指针找到中间节点
var getMiddleNode = function (head) {
    if (head === null || head.next === null) {
        return head
    }
    let slow = head
    let fast = head.next.next

    while (fast !== null && fast.next !== null) {
        slow = slow.next
        fast = fast.next.next
    }

    return slow
}

// 合并两个有序链表
var mergeTwoLists = function (l1, l2) {
    const dummy = new ListNode()
    let cur = dummy
    while (l1 && l2) {
        if (l1.val < l2.val) {
            [cur.next, l1] = [l1, l1.next]
        } else {
            [cur.next, l2] = [l2, l2.next]
        }
        cur = cur.next
    }
    cur.next = l1 ? l1 : l2
    return dummy.next
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant