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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
typedef struct ListNode Node;
struct ListNode* oddEvenList(struct ListNode* head ) {
    // write code here
    Node* odd=NULL;//记录奇数节点
    Node* even=NULL;//记录偶数节点
    Node* evenhead=NULL;//偶数的头节点
    Node* oddhead=NULL;//奇数的头节点
    Node* p=head;//运行的指针
    int n=1;//指针开头的位置
    if(head==NULL||head->next==NULL){
        return head;
    }
    while(p){
        if(n%2!=0){//奇数指针
            if(odd==NULL){
                odd=oddhead=p;//如果是空指针,要把头指针存好
            }else{
                odd->next=p;
                odd=p;//如果不是空指针，就接着odd
            }
        }else{
            if(even==NULL){
                even=evenhead=p;
            }else{
                even->next=p;
                even=p;
            }
        }
        p=p->next;//将指针向后延伸
        n++;//记录节点所在的位置
    }
    if(even){
        even->next=NULL;
    }//将偶数位指针指向空
   
    odd->next=evenhead;//奇数位指针指向偶数指针的头指针
    return oddhead;//返回头指针
}

所有返回的指针必须在头节点的位置