算法题练习——JS Node+python题解NC78 反转链表、NC140 排序

Love The Way You Lie 2024-04-08 13:20 72阅读 0赞

**目录**

NC78 反转链表

NC140 排序

--------------------

### NC78 反转链表 ###

**描述**

> 给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

> 数据范围：10000≤n≤1000
> 
> 要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

> 如当输入链表\{1,2,3\}时，
> 
> 经反转后，原链表变为\{3,2,1\}，所以对应的输出为\{3,2,1\}。
> 
> 以上转换过程如下图所示：

![180e1e7f07cc40df85e8f41e8a39f734.png][]

**示例1**

> 输入：\{1,2,3\}
> 
> 返回值：\{3,2,1\}

**示例2**

> 输入：\{\}
> 
> 返回值：\{\}
> 
> 说明：空链表则输出空

**JavaScript Node题解：**

/*function ListNode(x){
        this.val = x;
        this.next = null;
    }*/
    function ReverseList(pHead)
    {
        // write code here
        let pre = null;
        let cur = pHead;
        while(cur){
            let next = cur.next;
            cur.next = pre;//反转当前节点
            pre = cur;//前置节点后移
            cur = next;//当前结点后移
        }
        return pre
    }
    module.exports = {
        ReverseList : ReverseList
    };

**python代码解：**

# class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    #
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param head ListNode类 
    # @return ListNode类
    #
    class Solution:
        def ReverseList(self , head: ListNode) -> ListNode:
            # write code here
            if not head:
                return
            cur = head
            pre = None
            while cur:
                next = cur.next
                cur.next = pre
                pre = cur
                cur = next
            return pre

--------------------

### NC140 排序 ###

**描述**

> 给定一个长度为 n 的数组，请你编写一个函数，返回该数组按升序排序后的结果。

> 数据范围：0≤n≤1×10^3，数组中每个元素都满足0≤val≤10^9
> 
> 要求：时间复杂度 O(n^2)，空间复杂度 O(n)
> 
> 进阶：时间复杂度 O(nlogn)，空间复杂度 O(n)

> 注：本题数据范围允许绝大部分排序算法，请尝试多种排序算法的实现。

**示例1**

> 输入：\[5,2,3,1,4\]
> 
> 返回值：\[1,2,3,4,5\]

**示例2**

输入：\[5,1,6,2,5\]

返回值：\[1,2,5,5,6\]

**JavaScript Node题解：**

/**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    function MySort( arr ) {
        // write code here
        return arr.sort((a,b) => a-b)
    }
    module.exports = {
        MySort : MySort
    };

**python代码解：**

#
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 将给定数组排序
    # @param arr int整型一维数组 待排序的数组
    # @return int整型一维数组
    #
    class Solution:
        def MySort(self , arr: List[int]) -> List[int]:
            # write code here
            arr.sort()
            return arr

[180e1e7f07cc40df85e8f41e8a39f734.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/1769de24c46c45d48292c3eb8ab8b58e.png