奇偶链表 - lifengyu360/lifengyu_first_git_test GitHub Wiki

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL 示例 2:

输入: 2->1->3->5->6->4->7->NULL 输出: 2->3->6->7->1->5->4->NULL

/**

• Definition for singly-linked list.
• struct ListNode {

• int val;
  

• ListNode *next;
  

• ListNode() : val(0), next(nullptr) {}
  

• ListNode(int x) : val(x), next(nullptr) {}
  

• ListNode(int x, ListNode *next) : val(x), next(next) {}
  

• };

*/

class Solution {

public:

ListNode* oddEvenList(ListNode* head) {

    if ((head == nullptr) ||(head->next == nullptr)){
        return head;
    }

    int i = 0;
    ListNode *jishu_head = head;
    ListNode *jishu   = head;
   
    ListNode *oshushu = head->next;
    ListNode *oushu_head = oshushu;

    head = oshushu->next;   
    ListNode *tmp   = head;
    while (head) {
        if (0 == (i%2)){
            jishu->next =  head;
            head = head->next;
            jishu = jishu->next;
        }else {
            oshushu->next = head;
            head = head->next;
            oshushu = oshushu->next;
        }
        i++;
    }

    jishu->next = oushu_head;
    oshushu->next = nullptr;

    return jishu_head;
}

};