Leetcode - binary-tree-zigzag-level-order-traversal

Leetcode - sort-list

violet posted @ Mar 13, 2020 01:48:14 AM in 胡扯 with tags Algorithm merge sort ruby , 459 阅读

https://leetcode.com/problems/sort-list/

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val)
#         @val = val
#         @next = nil
#     end
# end

# @param {ListNode} head
# @return {ListNode}
def sort_list(head)
    return head if head == nil || head.next == nil
    
    fast = head
    slow = head
    tail = slow
    while fast != nil
        fast = fast.next
        fast = fast.next if fast != nil
        tail = slow
        slow = slow.next
    end
    left = head
    tail.next = nil
    right = slow
    left_node = sort_list(left)
    right_node = sort_list(right)
    return merge(left_node, right_node)
end

def merge(left, right)
    l = left
    r = right
    head = ListNode.new(0)
    node = head
    while l != nil && r != nil
        if l.val < r.val
            node.next = l
            l = l.next
        else
            node.next = r
            r = r.next
        end
        node = node.next
    end
    if l != nil
        node.next = l
    end
    if r != nil
        node.next = r
    end
    return head.next
end

相关文章
全局相关文章

[回复]

Bihar Board 12th Que 说:
Aug 17, 2022 08:45:39 PM

The question paper for the next class 12 final examinations in 2023 has been announced by the Bihar School Examination Board in Patna. Since then, the following pupils have been waiting for the entrance card. Later, the board will release the Important Question Papers; in the meanwhile, applicants can obtain the BSEB 12th Exam New Model Paper 2023, BSEB 12th Sample Question Paper 2023, or BSEB 12th Exam Guess Paper 2023 from the official website or from the URL that we have provided below. Bihar Board 12th Question Paper 2023 In the month of February 2023, the board will administer tests to all candidates who are enrolled in Bihar. Bihar Board also offers following the conclusion of the final examination and after results.

[回复]