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

题目描述

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

image-20250416173609218

思路分析

  • 将链表按照奇数位和偶数位分隔为两个链表
  • 反转偶数位链表
  • 合并两个有序链表

参考代码



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50



// 排序奇升偶降链表
func sortOddEvenList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
       return head
    }

    // 拆分奇偶链表
    odd, even := head, head.Next
    oddHead, evenHead := odd, 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 // 非常重要

    // 反转偶数链表
    var pre *ListNode
    cur := evenHead
    for cur != nil {
       next := cur.Next
       cur.Next = pre
       pre = cur
       cur = next
    }
    evenHead = pre

    // 合并两个链表
    dummy := &ListNode{}
    cur = dummy
    l1, l2 := oddHead, evenHead
    for l1 != nil && l2 != nil {
       if l1.Val < l2.Val {
          cur.Next = l1
          l1 = l1.Next
       } else {
          cur.Next = l2
          l2 = l2.Next
       }
       cur = cur.Next
    }
    if l1 != nil {
       cur.Next = l1
    } else if l2 != nil {
       cur.Next = l2
    }
    return dummy.Next
}

➡️ 点击查看完整代码



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80



package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

// 排序奇升偶降链表
func sortOddEvenList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
       return head
    }

    // 拆分奇偶链表
    odd, even := head, head.Next
    oddHead, evenHead := odd, 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 // 非常重要

    // 反转偶数链表
    var pre *ListNode
    cur := evenHead
    for cur != nil {
       next := cur.Next
       cur.Next = pre
       pre = cur
       cur = next
    }
    evenHead = pre

    // 合并两个链表
    dummy := &ListNode{}
    cur = dummy
    l1, l2 := oddHead, evenHead
    for l1 != nil && l2 != nil {
       if l1.Val < l2.Val {
          cur.Next = l1
          l1 = l1.Next
       } else {
          cur.Next = l2
          l2 = l2.Next
       }
       cur = cur.Next
    }
    if l1 != nil {
       cur.Next = l1
    } else if l2 != nil {
       cur.Next = l2
    }
    return dummy.Next
}

// 打印链表
func printList(head *ListNode) {
    cur := head
    for cur != nil {
       fmt.Print(cur.Val, " -> ")
       cur = cur.Next
    }
    fmt.Println("NULL")
}

func main() {
    // 示例链表
    head := &ListNode{1, &ListNode{8, &ListNode{3, &ListNode{6, &ListNode{5, &ListNode{4, &ListNode{7, &ListNode{2, nil}}}}}}}}
    fmt.Println("原链表:")
    printList(head)

    sortedHead := sortOddEvenList(head)
    fmt.Println("排序后的链表:")
    printList(sortedHead)
}

➡️ 点击查看 Java 题解



1



write your code here

相似题目

本文作者:
本文链接: https://hgnulb.github.io/blog/2025/20955637
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！