算法题练习——JS Node+python题解判断一个链表是否为回文结构、单链表的排序

﹏ヽ暗。殇╰゛Y 2024-04-05 05:29 49阅读 0赞

**目录**

判断一个链表是否为回文结构

单链表的排序

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

### 判断一个链表是否为回文结构 ###

**描述**

> 给定一个链表，请判断该链表是否为回文结构。
> 
> 回文是指该字符串正序逆序完全一致。

> 数据范围： 链表节点数 0≤n≤10^5，链表中每个节点的值满足 |val∣≤10^7

**示例1**

> 输入：\{1\}
> 
> 返回值：true

**示例2**

> 输入：\{2,1\}
> 
> 返回值：false
> 
> 说明：2->1

**示例3**

> 输入：\{1,2,2,1\}
> 
> 返回值：true
> 
> 说明：1->2->2->1

**JavaScript题解：**

/*
     * function ListNode(x){
     *   this.val = x;
     *   this.next = null;
     * }
     */
    
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    function isPail( head ) {
        // write code here
        let cur = head
        let temp = []
        while(cur){
            temp.push(cur.val)
            cur = cur.next
        }
        temp.reverse()
        cur = head
        for(let i=0; i<temp.length; i++){
            if(cur.val == temp[i]){
                cur = cur.next
            }else{
                return false
            }
        }
        return true
    }
    module.exports = {
        isPail : isPail
    };

**python题解：**

# class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    #
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param head ListNode类 the head
    # @return bool布尔型
    #
    class Solution:
        def isPail(self , head: ListNode) -> bool:
            # write code here
            cal = head
            temp = []
            while cal:
                temp.append(cal.val)
                cal = cal.next
            cal = head
            temp.reverse()
            for i in range(len(temp)-1):
                if temp[i] == cal.val:
                    cal = cal.next
                else:
                    return False
            return True

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

### 单链表的排序 ###

**描述**

> 给定一个节点数为n的无序单链表，对其按升序排序。

> 数据范围：0 < n \\le 1000000<n≤100000
> 
> 要求：时间复杂度 O(nlogn)O(nlogn)

**示例1**

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

**示例2**

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

**JavaScript题解：**

/*
     * function ListNode(x){
     *   this.val = x;
     *   this.next = null;
     * }
     */
    
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    function sortInList( head ) {
        // write code here
        let cur = head
        let temp = []
        while(cur){
            temp.push(cur.val)
            cur = cur.next
        }
        temp.sort((a,b)=>a-b)
        cur = head
        for(let i=0; i<temp.length-1; i++){
            cur.val = temp[i]
            let nex = cur.next
            nex.val = temp[i+1]
            cur = nex
        }
        return head
    }
    module.exports = {
        sortInList : sortInList
    };

**python题解：**

# class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    #
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param head ListNode类 the head node
    # @return ListNode类
    #
    class Solution:
        def sortInList(self , head: ListNode) -> ListNode:
            # write code here
            cur = head
            temp = []
            while cur:
                temp.append(cur.val)
                cur = cur.next
            temp.sort()
            cur = head
            for i in range(len(temp)-1):
                cur.val = temp[i]
                nex = cur.next
                nex.val =temp[i+1]
                cur = nex
            return head