leetcode【数据结构简介】《链表》卡片——双指针技巧

思路：
使用上文中的快慢指针方法：每次移动慢指针一步，而移动快指针两步。若quick->next!=NULL 和 quick->next->next!=NULL为NULL则返回false，否则直到quick追上slow。(而slow->next!=NULL是为了加一重保险毕竟循环体内出现了slow = slow->next;，但是删去了也没问题，毕竟他走的慢，即使有礁石，先触礁的也不是他)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    if(head==NULL) return false;	//特例判断
    struct ListNode *quick = head, *slow = head;
    while(quick->next!=NULL && quick->next->next!=NULL && slow->next!=NULL){
        if(quick->next==slow || quick->next->next==slow) return true;
        quick = quick->next->next;
        slow = slow->next;
    }
    return false;
}

2. 环形链表II

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

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

双指针法

思路：

特例判断

进入循环，快指针每次移动两个结点，慢指针每次移动一个结点，直到快指针不能继续(quick->next==NULL || quick->next->next==NULL)或者快指针追上慢指针(quick==slow)

慢指针slow不动，给快指针重新赋值为头指针quick = head;

快指针每次移动一个结点，慢指针每次移动一个结点，等快指针和慢指针相遇，此时就是我们要寻找的链表开始入环的第一个结点。

代码实现：

struct ListNode *detectCycle(struct ListNode *head) {
    if(head==NULL ) return NULL;
    if(head->next==NULL || head->next->next==NULL) return NULL;

    struct ListNode *quick = head, *slow = head;
    while(quick->next!=NULL && quick->next->next!=NULL){
        quick = quick->next->next;
        slow = slow->next;
        if(quick->next==NULL || quick->next->next==NULL) return NULL;
        if(quick==slow) break;
    }
    quick = head;

    while(quick!=slow){
        quick = quick->next;
        slow = slow->next;
    }
    return quick;
}

leetcode【数据结构简介】《链表》卡片——双指针技巧

对于小白来说，很可能看到这个函数的返回值类型struct ListNode *detectCycle(struct ListNode *head);会有点发懵。因为以前遇到的都是诸如int a(...);， char a(...);以及void a(...);之类，从来没有遇到过别的，但现在，不就遇到了嘛~
记住：函数的返回值类型类型是什么，咱就返回什么！比如对于这个函数来说我们就应该返回一个节点，而非一个索引(索引类型为int)。

3. 相交链表

编写一个程序，找到两个单链表相交的起始节点。
leetcode【数据结构简介】《链表》卡片——双指针技巧
注意：

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

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

暴力法

思路：

特例判断：两个指针为空

A链表只有一个节点

A链表不止一个节点(分为 B链表是否是一个节点两种情况）
因为while的条件判断为a->next!=NULL，而如果相交的起始节点为A的最后一个节点的情况（此时B链表只有一个节点），我们需要在while循环外面return a;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA==NULL || headB==NULL) return NULL;
    struct ListNode *a=headA, *b=headB;
    
    if(a->next==NULL){
        while(b->next!=NULL && b!=a) b = b->next;
        if(a==b) return a;
        else return NULL;
    }

    while(a->next!=NULL){
        b = headB;
        if(b->next!=NULL){
            while(b->next!=NULL && b!=a) b = b->next;
            if(b==a) return a;
        }
        else if(b==a) return a;
        a = a->next;
    }
    if(b==a) return a;
    return NULL;
}

leetcode【数据结构简介】《链表》卡片——双指针技巧

简单直接，应该是大家脑子跳出来的第一种方法，但是从数据可以看出，该种方法执行用时长得不得了，定然不是最优算法（不然那些95%的宝贝怎么就执行时间那么短呢~）。下面将介绍另外一种方法：双指针法。

双指针法

思路详解-传送门

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA==NULL || headB==NULL) return NULL;
    if(headA==headB) return headA;
    struct ListNode *a=headA, *b=headB;
    while(a!=b){
        a = a==NULL? headB: a->next;
        b = b==NULL? headA: b->next;
        if(a==b) return a;
    }
    return NULL;
}

leetcode【数据结构简介】《链表》卡片——双指针技巧

4. 删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

【说明】给定的 n 保证是有效的。

【进阶】尝试使用一趟扫描实现。

想法：

首先，链表具有单方向性，所以只能从前往后到达倒数第N个节点。

那么思路跳上心头：先遍历一遍得到节点的总个数N，然后减一减，不就可以计算出待删除点的正序索引了吗？

当然啦，这种方法自然是OK的，就是执行时间长了些。

尤其是在看到题目里还给了【进阶】的提示，结合本章标题“双指针技巧”以及之前在《数组与字符串》卡片的相关学习经历，一个极妙的想法涌上心头~这就是下面将要介绍的 固定长度的窗口滑动法 。

固定长度的窗口滑动法

思路：
我们让两个指针在链表上滑动，其中一个指针right（美其名曰”先行者“），先沿着链表滑动n个节点。接下来会遇到两种情况：

此时滑动到了最后一个节点right->next==NULL，那么我们就删除头节点；

此时如果先行者right并不是链表的最后一个节点，那么我们就在链表头最开始的地方，添加一个落后者left，先行者right和落后者left以同样速率在跑道链表上奔跑，直到先行者right到达终点right->next==NULL。此时，落后者left所在节点的下一个节点就是我们需要删除的节点。

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    if(!n) return head;
    struct ListNode* left=head, * right=head;
    for(int i=0; i<n; i++) right = right->next;
    if(right==NULL){
        struct ListNode* p=head;
        head = head->next;
        free(p);
        return head;
    }
    while(right->next!=NULL){
        left = left->next;
        right = right->next;
    } 
    struct ListNode* p=left->next;
    left->next = p->next;
    free(p);
    return head;
}

leetcode【数据结构简介】《链表》卡片——双指针技巧
需要注意的是：不要忘记考虑先行者right跑到终点而落后者left还没出发的情况。
吐槽：这是我目前为止遇到中等难度题目中最简单的了。

小结 - 链表中的双指针

提示

它与我们在数组中学到的内容类似。但它可能更棘手而且更容易出错。你应该注意以下几点：

在调用 next 字段之前，始终检查节点是否为空。
获取空节点的下一个节点将导致空指针错误。例如，在我们运行 fast = fast.next.next 之前，需要检查 fast 和 fast.next 不为空。
仔细定义循环的结束条件。

复杂度分析

空间复杂度分析容易。如果只使用指针，而不使用任何其他额外的空间，那么空间复杂度将是 O(1)。但是，时间复杂度的分析比较困难。为了得到答案，我们需要分析运行循环的次数。

在前面的查找循环示例中，假设我们每次移动较快的指针 2 步，每次移动较慢的指针 1 步。

如果没有循环，快指针需要 N/2 次才能到达链表的末尾，其中 N 是链表的长度。
如果存在循环，则快指针需要 M 次才能赶上慢指针，其中 M 是列表中循环的长度。

显然，M <= N 。所以我们将循环运行 N 次。对于每次循环，我们只需要常量级的时间。因此，该算法的时间复杂度总共为 O(N)。

可以通过分析其他问题以提高分析能力。别忘了考虑不同的条件。如果很难对所有情况进行分析，请考虑最糟糕的情况。