24/25/26,环形链表Ⅰ/Ⅱ/相交链表/链表突击

环形链表

给定一个链表，判断链表中是否有环。

进阶：
你能否不使用额外空间解决此题？
思路：两个指针，一个一次前进两步一个，如果有一时刻两个相交说明有环。
时间复杂度：O(n)。两链表只需要循环一遍
空间复杂度：O(1)只需要保存两个指针

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL||head->next == NULL)return false;
        ListNode*a,*b;
        a= head;
        b = a->next;
        while(true){
            if(b->next == NULL)return false;
            b = b->next;
            if(b->next == NULL)return false;
            b = b->next;
            a = a->next;
            if(b ==a)return true;
            
        }
        return false;
    }
};

环形链表Ⅱ

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

说明：不允许修改给定的链表。

进阶：
你是否可以不用额外空间解决此题？

思路：前半部分同上题，确定有环后，两个指针继续一次2步/一次1步地前进，记录再次相遇时经过的移动的次数n，此时该次数n就为环的节点数，那么将a指向头部，将b指向a的后第n个节点，同时每次各走一步，当相遇时即为第一个入环点。
时间复杂度：O(n)。
空间复杂度：O(1)

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL||head->next == NULL)return NULL;
        ListNode*a,*b;
        a= head;
        b = a->next;
        int i=0;
        while(true){
            if(b->next == NULL)return NULL;
            b = b->next;
            if(b->next == NULL)return NULL;
            b = b->next;
            a = a->next;
            if(b ==a){
                
                b = b->next; 
                b = b->next;
                a = a->next;
                i++;
                while(a != b){
                    b = b->next; 
                    b = b->next;
                    a = a->next;
                    i++;
                }
                break;
            }
            
        }
        
        a = head;
        b = a;
        while(i>0){
            b = b->next;
            i--;
        }
        
        while(a != b){
            a =a->next;
            b = b->next;
        }
        return a;
        
        
    }
};

相交链表

编写一个程序，找到两个单链表相交的起始节点。

例如，下面的两个链表：

A:          a1 → a2
                   ↘
                    c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
在节点 c1 开始相交。

注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

思路：题目只要求返回结果时保持原结构，那么耍个小聪明，运算时将a链的尾部指向b的头部，那么如果不相交就不带环，相交就变成了如上题的带环链表，交点就是入环点，所以解法如上题，先检测是否有环（是否相交），再检测入环点（相交点），最后返回的时候别忘了将链表改回来。
时间复杂度：O(n)。
空间复杂度：O(1)

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == NULL || headB == NULL)return NULL;
        
        ListNode*a,*b,*aa;
        
        aa = headA;
        b = headB;
        while(aa->next != NULL){
            aa = aa->next;
        }
        
        aa->next = b;
        
        
        
        
        
        a= headA;
        b = a->next;
        int i=0;
        while(true){
            if(b->next == NULL){
                aa->next = NULL;
                return NULL;
            }
            b = b->next;
            if(b->next == NULL){
                aa->next = NULL;
                return NULL;
            }
            b = b->next;
            a = a->next;
            if(b ==a){
                
                b = b->next; 
                b = b->next;
                a = a->next;
                i++;
                while(a != b){
                    b = b->next; 
                    b = b->next;
                    a = a->next;
                    i++;
                }
                break;
            }
            
        }
        
        a = headA;
        b = a;
        while(i>0){
            b = b->next;
            i--;
        }
        
        while(a != b){
            a =a->next;
            b = b->next;
        }
        aa->next = NULL;
        return a;
            
        
    }
};