Skip to main content

148. Sort List

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

Python​

Convert to Array than build Linked List back​

  • Time: O(N)
  • Space: O(N)
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        elements = []

        cur = head
        while cur:
            elements.append(cur.val)
            cur = cur.next
        elements.sort(reverse=True)

        new_head = ListNode()
        cur = new_head
        while elements:
            elm = elements.pop()
            cur.next = ListNode(val=elm)
            cur = cur.next

        return new_head.next

Rust​

Convert to Array than build Linked List back​

impl Solution {
    pub fn sort_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut vec: Vec<i32> = vec![];
        while let Some(mut node) = head {
            vec.push(node.val);
            head = node.next;
        }
        vec.sort();
        let mut next = None;
        while let Some(val) = vec.pop() {
            next = Some(Box::new(ListNode{next, val}))
        }
        next
    }
}