Leetcode.328.Odd Even Linked Lis

题目

给定一个链表，调整链表元素位置，将偶数位的节点放到链表前面，将奇数位的节点放到链表后面。

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL
Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

思路

将偶数节点和奇数节点分别组成两个新的链表，最后再将两个链表合并起来。

ListNode* oddEvenList(ListNode* head) {
    if (head == nullptr) return head;
    ListNode *res = head;

    ListNode *odd = head;
    ListNode *oddHead = head;
    head = head->next;
    odd->next = nullptr;
    if (head == nullptr) {
        return res;
    }
    ListNode *even = head;
    ListNode *evenHead = head;
    head = head->next;
    even->next = nullptr;

    int i = 0;
    while (head != nullptr) {
        if (i++ % 2 == 1) {
            even->next = head;
            head = head->next;
            even = even->next;
            even->next = nullptr;
        } else {
            odd->next = head;
            head = head->next;
            odd = odd->next;
            odd->next = nullptr;
        }
    }

    odd->next = evenHead;
    return oddHead;
}

总结

链表的操作比较微妙，注意操作顺序。