328. 奇偶链表

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

分离出奇偶链表然后合并

原始链表的头节点 head 也是奇数链表的头节点以及结果链表的头节点，head->next是偶数链表的头节点

方法:

• 维护两个指针 odd 和 even 分别指向奇数节点和偶数节点，初始时 odd = head，even = evenHead。通过迭代的方式将奇数节点和偶数节点分离成两个链表，每一步首先更新奇数节点，然后更新偶数节点
  • 更新奇数节点时，奇数节点的后一个节点需要指向偶数节点的后一个节点，因此令 odd.next = even.next，然后令 odd = odd.next，此时 odd 变成 even 的后一个节点
  • 更新偶数节点时，偶数节点的后一个节点需要指向奇数节点的后一个节点，因此令 even.next = odd.next，然后令 even = even.next，此时 even 变成 odd 的后一个节点

全部节点分离完毕的条件是 even 为空节点或者 even.next 为空节点，此时 odd 指向最后一个奇数节点（即奇数链表的最后一个节点） 最后令 odd.next = evenHead将偶数链表连接在奇数链表之后，即完成了奇数链表和偶数链表的合并，结果链表的头节点仍然是 head

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        //如果链表为空 || 只有一个节点就不需要操作了
        if(head == nullptr || head->next == nullptr)
        {
            return head;
        }
        ListNode* odd = head;//头节点是奇数链表的第一个节点
        ListNode* even =head->next;//头节点的下一个节点是偶数链表的第一个节点
        ListNode* evenHead = even;//记录偶链表的头！
        
        //even在前面走,终止条件是:even && even->next
        while(even && even->next)
        {
            //先链接奇数位节点,再链接偶数位节点
            //顺序为:odd even  此时even的下一个节点就是该让odd->next链接的,然后odd往后走
            odd->next = even->next;
            odd = odd->next;
            //更改之后顺序为:even odd  此时odd的下一个节点就是该让even->next链接的  然后even往后走
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenHead;//奇链表的尾链表偶链表的头
        return head;
    }
};

141.环形链表I

https://leetcode.cn/problems/linked-list-cycle/

方法1:使用set

使用容器 -> 不断遍历链表,把节点放到容器中,如果节点曾经在容器中出现过 -> 说明就是有环的！

class Solution {
public:
    bool hasCycle(ListNode *head) {
        //如果一个链表中有环，那么当遍历这个链表，进入环之后环中的节点就会一直循环被遍历
        //所以我们利用Set的特点，如果这个节点在Set中已经存在则说明这个链表存在环
        set<ListNode*> s;
        while(head)
        {
            //count:统计key值出现的次数 ,如果出现过,就会进入if内部
            if(s.count(head))
            {
                //说明该节点曾经遍历过->有环
                return true;
            }
            s.insert(head);//把当前节点放到set中
            head = head->next;
        }
        return false;
    }
};

方法2:快慢指针
fast一次走两步,slow一次走一步,如果有环,slow和fast就会相遇,因为fast比slow走的快,所以如果没有环,fast就会走到空

class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        
        //两个节点从头开始遍历
        ListNode* fast = head;
        ListNode* slow = head;
        //如果没有环,fast就会提前走到空->分为奇数节点和偶数节点的情况
        while(fast != NULL && fast->next!= NULL)
        {
             fast = fast->next->next;// fast一次走两步
            slow = slow->next;//slow一次走一步
            //这个判断不能放前面,因为一开始二者都是从头开始的 fast == slow
            //fast和slow相遇 -> 说明有环 
            if(fast == slow)
            {
                return true;
            }
        }
        return false;//说明没有环
    }
};