一、题目

一个链表，特点是奇数位升序偶数位降序，使得链表变成升序的。

1
2
3
1 200 2 100 3 50 4 30 5
===>
1 2 3 4 5 30 50 100 200

二、分析

这道题目三步走：

  • 首先根据奇数位和偶数位拆分成两个链表
  • 然后对偶数位链表进行反转
  • 最后将两个有序链表进行合并
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
struct Node {
    int val;
    Node* next;

    explicit Node(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    std::pair<Node*, Node*> split_lists(Node* head) {
        Node* head1 = nullptr;
        Node* head2 = nullptr;
        Node* cur1 = nullptr;
        Node* cur2 = nullptr;
        int count = 1;
        while (head != nullptr) {
            if (count % 2 == 1) {
                if (head1 == nullptr) {
                    cur1 = head;
                    head1 = cur1;
                } else {
                    cur1->next = head;
                    cur1 = cur1->next;
                }
            } else {
                if (head2 == nullptr) {
                    cur2 = head;
                    head2 = cur2;
                } else {
                    cur2->next = head;
                    cur2 = cur2->next;
                }
            }
            count++;
            head = head->next;
        }
        cur1->next = nullptr;
        cur2->next = nullptr;
        return std::pair<Node*, Node*>{head1, head2};
    }

    Node* reverse_list(Node* head) {
        Node* pre = nullptr;
        Node* next = nullptr;
        while (head != nullptr) {
            next = head->next;
            head->next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    Node* combine_list(Node* head1, Node* head2) {
        if (head1 == nullptr || head2 == nullptr) {
            return head1 != nullptr ? head1 : head2;
        }
        Node* head = head1->val < head2->val ? head1 : head2;
        Node* cur1 = head == head1 ? head1 : head2;
        Node* cur2 = head == head1 ? head2 : head1;
        Node* pre = nullptr;
        Node* next = nullptr;
        while (cur1 != nullptr && cur2 != nullptr) {
            if (cur1->val < cur2->val) {
                pre = cur1;
                cur1 = cur1->next;
            } else {
                next = cur2->next;
                pre->next = cur2;
                cur2->next = cur1;
                pre = cur2;
                cur2 = next;
            }
        }
        pre->next = cur1 == nullptr ? cur2 : cur1;
        return head;
    }
};