notes | Kisstar

# 328. 奇偶链表

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

# 解题思路

  • 遍历链表，并对当前节点的索引进行判断，如果是奇数就将其移动到奇数项的末尾，并更新奇数的末尾，如果是偶数则保持不动。
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        ListNode* new_head = new ListNode(0, head);
        ListNode* last_odd = new_head;
        ListNode* prev = new_head;
        ListNode* cur = head;
        ListNode* next;
        bool has_even = false;
        int i = 1;

        while (cur) {
            if ((i++ % 2 != 0)) {
                // 奇数
                if (has_even) {
                    next = cur->next;
                    prev->next = next;
                    cur->next = last_odd->next;
                    last_odd->next = cur;
                    last_odd = cur;
                    // prev = cur;
                    cur = next;
                } else {
                    last_odd = cur;
                    prev = cur;
                    cur = cur->next;
                }
            } else {
                prev = cur;
                cur = cur->next;
                has_even = true;
            }
        }

        return new_head->next;
    }
};

另外，因为相邻节点的奇偶性不同，所以可以将奇数节点和偶数节点分离成奇数链表和偶数链表，然后将偶数链表连接在奇数链表之后，合并后的链表即为结果链表。具体可参考官方题解。

# 参考

← 集合 →