LeetCode328奇偶链表

题目链接

https://leetcode-cn.com/problems/odd-even-linked-list/

题解

• 我自己写的
• 思路是：首先建立两个链表（奇数号结点链表和偶数号结点链表），然后遍历整个链表并通过尾插法构造这两个链表，最后将偶数号结点链表连接到奇数号结点链表尾部即可。
• 时间复杂度是$O(n)$，空间复杂度是$O(1)$
• 具体思路见代码注释

// Problem: LeetCode 328
// URL: https://leetcode-cn.com/problems/odd-even-linked-list/
// Tags: Linked List
// Difficulty: Medium

struct ListNode{
    int val;
    ListNode* next;
};

class Solution{
public:
    ListNode* oddEvenList(ListNode* head) {
        // 处理0个、1个或者2个结点的情况
        if (head == nullptr || head->next == nullptr || head->next->next == nullptr)
            return head;
        // 奇数号结点链表首尾
        ListNode *oddHead = head, *oddTail = oddHead;
        // 偶数号结点链表首尾
        ListNode *evenHead = head->next, *evenTail = evenHead;
        // 当前结点是第奇数个还是偶数个，true则为第奇数个，false则为第偶数个
        bool oddFlag = true;
        // 从第三个结点开始遍历
        head = head->next->next;
        // 遍历链表，将链表分为奇数号结点链表和偶数号结点链表
        while(head != nullptr){
            if(oddFlag==true){
                oddTail->next = head;
                oddTail = oddTail->next;
            }
            else{
                evenTail->next = head;
                evenTail = evenTail->next;
            }
            oddFlag = !oddFlag;
            head = head->next;
        }
        // 连接奇数号结点链表和偶数号结点链表
        oddTail->next = evenHead;
        evenTail->next = nullptr;
        return oddHead;
    }
};

---

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!

---