算法题练习——JS Node+python题解合并k个已排序的链表及链表的奇偶重排

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