跟我坚持刷leetcode（第二天-奇偶链表）

对抗惰性，从今天做起。坚持每天刷leetcode并附带一个题的题目，思路，代码。感兴趣的小伙伴一起坚持来吧(c代码，不过思路都是差不多的)。

题目(难度中等):
给出一个单链表，把奇数位置的节点连接在一起，后面跟着连接在一起的偶数位置节点(注意奇偶指的是节点的位置，而不是节点内的值)。时间要求：O（nodes）。
空间要求：O(1)。
例子：

输入：1->2->3->4->5->NULL
输出：1->3->5->2->4->NULL

输入：1->4->6->2->3->NULL
输出：1->6->3->4->2->NULL
思路：
1.不好的思路：原地改变，把所有奇数位置的节点一个一个往前移动，随着移动的进行，当前奇数位到下一个奇数位之间的节点会越来越多。首先不满足时间要求，其次需要变量记录两个奇数位之间距离。
2.正确（未必最优）思路：用两个链表，先考虑一下特殊情况（空链表或者长度为1）。
两个链表的头结点分别是原链表的第一个和第二个节点。然后原head节点不断向后移动。第一次把节点接在第一个链表后面，第二次接在第二个链表后面。不断循环，直至head为NULL。最后把b接在a的后面。处理一下尾节点就好了。
/其实第二种思路包含了弹出栈的数据结构/
代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* oddEvenList(struct ListNode* head) {
    struct ListNode* a = NULL;
    struct ListNode* b = NULL;
    if(head!=NULL)
    {
        a = head;
        head = head->next;
    }
    else
    return NULL;
    if(head!=NULL)
    {
        b = head;
        head = head->next;
    }
    else
    return a;
    int i = 0;
    struct ListNode* aptr = a;
    struct ListNode* bptr = b;
    while(head!=NULL)
    {
        if(i%2==0)
        {
            aptr->next = head;
            aptr = aptr->next;
            head = head->next;
        }
        else
        {
            bptr->next = head;
            bptr = bptr->next;
            head = head->next;
        }
        i++;
    }
    aptr->next = b;
    bptr->next = NULL;
    return a;
}