题解 | #链表的奇偶重排#

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) {
        // write code here

        if (head == nullptr || head->next == nullptr) return head;
        ListNode* odd = head;
        // ListNode* l1_head=odd;
        ListNode* even = head->next;
        ListNode* l2_head = even;
        while (even && even->next) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
            // head=head->next->next;
        }

        odd->next = l2_head;

        return head;




    }
};

就是取奇数位先排，后放偶数位。链表的头为第一个奇数位，只要每次往后移动两个就是下一个奇数位。head->next是第一个偶数位。

    while (even && even->next) {
        odd->next = even->next;
        odd = odd->next;
        even->next = odd->next;
        even = even->next;
        // head=head->next->next;
    }

奇数位的第一个是head,偶数位的第一个是head->next;那么奇数位的下一个就是head->next->next也就是偶数位的下一个、所以

odd->next=even->next; 此时odd下一个已知。后续还是往后加，odd=odd->next;指针指向下一个。同理。偶数的下一个也就是当前奇数位的下一个。 even->next = odd->next; 后续还是往后加，even = even->next;指针指向下一个。这样直到循环结束，此时就有了奇数位和偶数位的两条链，在把偶数位的链接到奇数位后面，返回整条链。