题目描述

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

 

题目大意

将一个链表重新排序，按照奇数位置的节点按原来顺序排在前边，偶数位置的节点按照原来顺序排在后边。

（要求时间复杂度为O（N），空间复杂度为O（1））

 

示例

E1

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

E2

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

 

解题思路

利用两个指针分别指向偶数节点和奇数节点位置，依次重新组合链表，最后将偶数位的头节点连到奇数位的末尾。

 

复杂度分析

时间复杂度：O(N)

空间复杂度：O(1)

 

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head == NULL)
            return head;
        // 分别存储奇数头节点，奇数当前结点，偶数头节点，偶数当前结点
        ListNode* ohead;
        ListNode* ehead;
        ListNode* ocur;
        ListNode* ecur;
        ohead = head; ocur = head;
        ehead = head->next; ecur = head->next;
        head = head->next;
        // 若链表节点个数大于1个
        if(head) {
            head = head->next;
            // flag表示当前访问的是否为奇数节点
            bool flag = true;
            // 依次访问链表各个节点
            while(head != NULL) {
                // 若当前节点位奇数位节点
                if(flag) {
                    ocur->next = head;
                    ocur = ocur->next;
                    flag = false;
                }
                // 否则为偶数位节点
                else {
                    ecur->next = head;
                    ecur = ecur->next;
                    flag = true;
                }
                head = head->next;
            }
            // 将偶数位头节点连接到奇数位链表末尾
            ocur->next = ehead;
            ecur->next = NULL;
        }
        
        return ohead;
    }
};