排序奇升偶降链表

[编程题]排序奇升偶降链表

热度指数：3181 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个奇数位升序，偶数位降序的链表，返回对其排序后的链表。

题面解释：例如链表 1->3->2->2->3->1 是奇数位升序偶数位降序的链表，而 1->3->2->2->3->2 则不符合题目要求。

数据范围：链表中元素个数满足 $1 \le n \le 10000 \$ ，链表中的元素大小满足 $1 \le val \le 100000 \$

示例1

输入

{1,3,2,2,3,1}

输出

{1,1,2,2,3,3}

示例2

输入

{1,2,2}

输出

{1,2,2}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

今天无bug_

func sortLinkedList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	var jishu []int
	var oushu []int
	num := 1
	for head != nil {
		if num%2 == 0 {
			oushu = append(oushu, head.Val)
		} else {
			jishu = append(jishu, head.Val)
		}
		head = head.Next
		num++
	}

	sort.Slice(jishu, func(i, j int) bool {
		return jishu[i] < jishu[j]
	})
	sort.Slice(oushu, func(i, j int) bool {
		return oushu[i] > oushu[j]
	})

	var ret []int
	for i := 0; i < len(jishu); i++ {
		ret = append(ret, jishu[i])
		if i < len(oushu) {
			ret = append(ret, oushu[i])
		}
	}
	var retNode *ListNode
	p := retNode
	for _, val := range ret {
		if retNode == nil {
			retNode = &ListNode{Val: val}
			p = retNode
		} else {
			retNode.Next = &ListNode{Val: val}
			retNode = retNode.Next
		}
	}
	return p
}

发表于 2025-03-25 15:29:19 回复(0)

小谷围做题家

package main

import "sort"
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
*/
func sortLinkedList( head *ListNode ) *ListNode {
    arr:=[]*ListNode{}
    for p:=head;p!=nil;p=p.Next{
        arr=append(arr,p)
    }
    sort.Slice(arr,func(i,j int)bool{
        return  arr[i].Val<arr[j].Val
    })
    for i,ln:=range arr{
        if i+1<len(arr){
            ln.Next=arr[i+1]
        }else{
            ln.Next=nil
        }
    }
    return arr[0]
}

发表于 2023-03-08 18:43:23 回复(0)