链表题练习——JS Node+python题解合并k个已排序的链表及链表的奇偶重排（CSDN编程竞赛）

- 日理万妓 2024-04-05 05:13 14阅读 0赞

> CSDN编程竞赛报名地址：https://edu.csdn.net/contest/detail/16

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

> 这次CSDN 的编程竞赛的题目相对很简单，四道编程题不用半小时就可以全部ak，9-18号11点前都能进行报名，得奖后有丰厚的奖励等你拿。错过的朋友可以等下一期。

> 本文给大家分享一道我在其他的编程比赛中遇到的一道链表题目，是不需要自己输入输出的，反倒让我刚开始有些无从下手，借故分享给大家，第二道也是正常的链表题，也呈现给大家。

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

**目录**

合并k个已排序的链表

链表的奇偶重排

总结

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

### 合并k个已排序的链表 ###

**描述**

> 合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

> 数据范围：节点总数满足0≤n≤10^5，链表个数满足1≤k≤10^5，每个链表的长度满足1≤len≤200 ，每个节点的值满足∣val∣<=1000；

> 要求：时间复杂度 O(nlogk)O(nlogk)

**示例1**

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

**示例2**

> 输入：\[\{1,2\},\{1,4,5\},\{6\}\]
> 
> 返回值：\{1,1,2,4,5,6\}

**JavaScript题解：**

/*
     * function ListNode(x){
     *   this.val = x;
     *   this.next = null;
     * }
     */
    
    /**
     * 
     * @param lists ListNode类一维数组 
     * @return ListNode类
     */
    function mergeKLists( lists ) {
        // write code here
        if(!lists) return null
        let listsval = []
        for(let i=0;i<lists.length;i++){
            while(lists[i]){
                listsval.push(lists[i].val)
                lists[i] = lists[i].next
            }
        }
        listsval.sort((a,b)=>a-b)
        let head = new ListNode(0)
       let cur = head
       listsval.forEach(item=>{
           cur.next = new ListNode(item);
           cur = cur.next
       })
        return head.next
    }
    module.exports = {
        mergeKLists : mergeKLists
    };

**python不用输入输出题解：**

# class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    #
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param lists ListNode类一维数组 
    # @return ListNode类
    #
    class Solution:
        def mergeKLists(self , lists: List[ListNode]) -> ListNode:
            # write code here
            if not lists:
                return None
            listNodeList = []
            listValList = []
            for head in lists:
                while head:
                    listNodeList.append(head)
                    listValList.append(head.val)
                    head = head.next
            listValList = sorted(listValList)
            head = listNodeList[0]
            for i in range(len(listValList)-1):
                cur = listNodeList[i]
                nex = listNodeList[i+1]
                cur.val = listValList[i]
                nex.val = listValList[i+1]
                cur.next = nex
            return head

**python自己输入输出题解：**

link_list = input()
    link_list = link_list.replace('[', '')
    link_list = link_list.replace(']', '')
    link_list = link_list.replace('{', '')
    link_list = link_list.replace('}', '')
    link_list = link_list.split(',')
    if link_list[0] == '':
        print('{}')
    else:
        nums = []
        for each in link_list:
            if each == '':
                continue
            nums.append(int(each))
        res = '{' + ','.join(map(str, sorted(nums))) + '}'
        print(res)

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

### **链表的奇偶重排** ###

**描述**

> 给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。

> 注意是节点的编号而非节点的数值。

> 数据范围：节点数量满足 0≤n≤10^5，节点中的值都满足0≤val≤1000
> 
> 要求：空间复杂度 O(n)，时间复杂度 O(n)

**示例1**

> 输入：\{1,2,3,4,5,6\}
> 
> 返回值：\{1,3,5,2,4,6\}
> 
> 说明：
> 
> 1->2->3->4->5->6->NULL
> 
> 重排后为
> 
> 1->3->5->2->4->6->NULL

**示例2**

> 输入：\{1,4,6,3,7\}
> 
> 返回值：\{1,6,7,4,3\}
> 
> 说明：
> 
> 1->4->6->3->7->NULL
> 
> 重排后为
> 
> 1->6->7->4->3->NULL  
> 奇数位节点有1,6,7，偶数位节点有4,3。重排后为1,6,7,4,3

**解析：**

>  *  step 1：判断空链表的情况，如果链表为空，不用重排。
>  *  step 2：使用双指针odd和even分别遍历奇数节点和偶数节点，并给偶数节点链表一个头。
>  *  step 3：上述过程，每次遍历两个节点，且even在后面，因此每轮循环用even检查后两个元素是否为NULL，如果不为再进入循环进行上述连接过程。
>  *  step 4：将偶数节点头接在奇数最后一个节点后，再返回头部。

**JavaScript题解：**

/*
     * function ListNode(x){
     *   this.val = x;
     *   this.next = null;
     * }
     */
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    function oddEvenList( head ) {
        // write code here
        if(!head)return
        let even = head.next
        let odd = head
        let evenhead =even
        while(even&&even.next){
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        }
        odd.next = evenhead
        return head
    }
    module.exports = {
        oddEvenList : oddEvenList
    };

**Python题解：**

class Solution:
        def oddEvenList(self , head: ListNode) -> ListNode:
             #如果链表为空，不用重排
            if head == None:
                return head
            #even开头指向第二个节点，可能为空
            even = head.next 
            #odd开头指向第一个节点
            odd = head 
            #指向even开头
            evenhead = even 
            while even and even.next:
                #odd连接even的后一个，即奇数位
                odd.next = even.next 
                #odd进入后一个奇数位
                odd = odd.next 
                #even连接后一个奇数的后一位，即偶数位
                even.next = odd.next 
                #even进入后一个偶数位
                even = even.next 
            #even整体接在odd后面
            odd.next = evenhead 
            return head

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

### **总结**  ###

> 程序员写代码并不是从0开始的，我们也是需要借助多个模板拼接，使得代码能够实现我们的想法，而且也并非默写出来，毕竟学习编程是开卷学习，开卷使用，写程序也是一样的，我们写完程序都需要去借鉴一下他人的作品，争取提升自己代码的质量，优化算法，才能使我们不断进步！！！