C语言重构【328】奇偶链表

╰+哭是因爲堅強的太久メ 2023-02-14 03:23 1阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
    
    请尝试使用原地算法完成。你的算法的空间复杂度应为 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; * struct ListNode *next; * }; */
    struct ListNode* oddEvenList(struct ListNode* head){ 
            //奇偶两条数组，最后合起来
            struct ListNode *cur = head;
            struct ListNode *oddNum,*oddHead;
            struct ListNode *evenNum,*evenHead;
            
            oddHead = (struct ListNode*)malloc(sizeof(struct ListNode));
            evenHead = (struct ListNode*)malloc(sizeof(struct ListNode));
            oddNum = oddHead;
            evenNum = evenHead;
            int tag = 0;
            while(cur!=NULL){ 
                //if old
                if(tag==0){     
                    oddNum->next = cur;
                    oddNum = oddNum->next;       
                    tag=1;
                }
                else if(tag==1){ 
                    //if even
                    evenNum->next = cur;
                    evenNum = evenNum ->next;    
                    tag=0;
                }
                cur = cur->next;
            }
            evenNum->next = NULL;
            //mix
            oddNum->next = evenHead->next;
            return oddHead->next;
    }

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1),新建两个头结点，俩指针

[Git]: https://github.com/ch98road/leetcode