Relocate List By Odd Or Even

发表于 | 分类于

Relocate List By Odd Or Even

题目描述：

给定链表的头节点，然后要求根据链表节点所处的位置的奇偶性重新排列链表。

例子：

具体描述可以看LeetCode328

解题思路：

本题的解题思路是将原始链表中的奇数位置节点连接成奇数链表，偶数位置连接成偶数链表；然后重新连接这两个链表即可。主要需要注意的是：在遍历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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next) return head;
        // 单个节点或者空链表直接返回
        ListNode* odd = head;
        ListNode* even = head->next;
        // 定义奇偶链表的头节点
        ListNode* even_head = even;
        ListNode* odd_head = odd;
        // 保存奇偶链表的头节点用于最后的连接
        while(odd->next && even->next){
            if (even->next){
                odd->next = even->next;
                odd = odd->next;
                // 连接奇数链表
            }
            if (odd->next){
                even->next = odd->next;
                even = even->next;
                //连接偶数链表
            }
        }
        even->next = NULL;
        odd->next = NULL;
        // 定义链表尾部节点
        odd->next = even_head;
        return odd_head;
    }
};