LeetCode 补充题 1. 排序奇升偶降链表

Categories:

题目描述
思路分析
1. 解法一：拆分 + 反转 + 合并（推荐）
相似题目

题目描述

✅ 补充题 1. 排序奇升偶降链表

思路分析

解法一：拆分 + 反转 + 合并（推荐）

核心思路：

奇数位链表单调递增，偶数位链表单调递减。

先按位置拆分为两条链表，再反转偶数位链表使其递增。

最后合并两条递增链表。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public ListNode sortOddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;

        while (even != null && even.next != null) {
            odd.next = odd.next.next;
            odd = odd.next;

            even.next = even.next.next;
            even = even.next;
        }
        odd.next = null;

        ListNode reversedEven = reverse(evenHead);
        return merge(head, reversedEven);
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    private ListNode merge(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) {
                cur.next = a;
                a = a.next;
            } else {
                cur.next = b;
                b = b.next;
            }
            cur = cur.next;
        }
        cur.next = a != null ? a : b;
        return dummy.next;
    }
}

func sortOddEvenList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	odd := head
	even := head.Next
	evenHead := even

	for even != nil && even.Next != nil {
		odd.Next = odd.Next.Next
		odd = odd.Next

		even.Next = even.Next.Next
		even = even.Next
	}
	odd.Next = nil

	reversedEven := reverse(evenHead)
	return mergeList(head, reversedEven)
}

func reverse(head *ListNode) *ListNode {
	var prev *ListNode
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = prev
		prev = cur
		cur = next
	}
	return prev
}

func mergeList(a *ListNode, b *ListNode) *ListNode {
	dummy := &ListNode{}
	cur := dummy

	for a != nil && b != nil {
		if a.Val <= b.Val {
			cur.Next = a
			a = a.Next
		} else {
			cur.Next = b
			b = b.Next
		}
		cur = cur.Next
	}

	if a != nil {
		cur.Next = a
	} else {
		cur.Next = b
	}

	return dummy.Next
}

相似题目

题目	难度	考察点
21. 合并两个有序链表	简单	链表合并
148. 排序链表	中等	链表排序
86. 分隔链表	中等	链表拆分
143. 重排链表	中等	链表操作
328. 奇偶链表	中等	链表操作

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/20955637