刷题使我快乐，满脸开心.jpg

• 来源：CodeTop
• 链接：https://mp.weixin.qq.com/s/0WVa2wIAeG0nYnVndZiEXQ

题目

链表，奇数位置按序增长，偶数位置按序递减，如何能实现链表从小到大？（2020.10 字节跳动-后端）

奇偶生序倒序链表的重新排序组合，例如：18365472（2020.08 字节跳动-后端）

1->4->3->2->5 给定一个链表奇数部分递增，偶数部分递减，要求在O(n)时间复杂度内将链表变成递增，5分钟左右（2020.07 字节跳动-测试开发）

奇数位升序偶数位降序的链表要求时间O(n)空间O(1)的排序？(2020.07 字节跳动-后端)

示例 1：

输入：1->8->3->6->5->4->7->2->NULL
输出：1->2->3->4->5->6->7->8->NULL

思路

这道题难度应该是中等没啥问题，其实涉及的思路都比较基础，就是

• 拆分链表
• 反转偶数链表（转为升序）
• 合并链表

感觉无需说太多，主要是冷静分析，以及必要时一定不要单纯想象，实际画图模拟下~

代码

func do(root *ListNode) *ListNode {
	if root == nil || root.Next == nil {
		return root
	}
	veryHead1 := &ListNode{}
	veryHead2 := &ListNode{}
	head1 := veryHead1
	head2 := veryHead2

	// 拆分双链
	i := 1
	for root != nil {
		if i%2 == 1 {
			head1.Next = root
			head1 = head1.Next
		} else {
			head2.Next = root
			head2 = head2.Next
		}
		root = root.Next
		i++
	}
	// 尾部清空，可能会因为指针引用地址没有变，造成混乱
	head1.Next = nil
	head2.Next = nil

	// 翻转偶数链
	// 为了清晰，不复用变量
    now := veryHead2.Next
	var pre, next *ListNode
	for now != nil {
		next = now.Next
		now.Next = pre
		pre = now
		now = next
	}

	// 合并链表
    // 为了清晰，不复用变量
	veryHead := &ListNode{}
	head := veryHead
	head1 = veryHead1.Next
	head2 = pre
	for head1 != nil && head2 != nil {
		if head1.Val > head2.Val {
			head.Next = head2
			head2 = head2.Next
		} else {
			head.Next = head1
			head1 = head1.Next
		}
		head = head.Next
	}
    // 当有一个链空了，剩下的直接串上就好
	if head1 == nil {
		head.Next = head2
	} else if head2 == nil {
		head.Next = head1
	}
	return veryHead.Next
}