快慢指针的算法应用

数据结构

快慢指针主要解决的问题：

1. 寻找/删除第K个节点；
2. 有关链表环问题解法：寻找/删除第K个节点。

问题一： 给定任意一个有序数组，计算出去重后的数组长度, 要求：只能在原数组中进行更改

去重数组长度

// Objective-C
+ (int)removeDupllcates:(NSMutableArray*)nums {
    if (nums.count==0) return 0;
    
    int slow = 0;
    for (int fast=0; fast<nums.count; fast++) {
        if (nums[slow] != nums[fast]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    NSLog(@"--- slow: %d， result: %@", slow, nums);
    return slow+1;
}

+ (int)solutionDupllcates:(NSMutableArray*)nums {
    int slow = 0, fast = 0;
    
    while (true) {
        fast++;  // 快指针向右移动
        
        // 快指针移动到数组末尾则退出，说明数组元素完成判断去重
        if (fast >= nums.count) {
            break;
        }
        if (nums[fast] == nums[slow]) {
            continue;  // 慢指针与快指针指向元素相同，说明重复元素；快指针继续向h右移动。
        } else {
            // 慢指针与快指针指向元素不同；则将快指针元素复制到慢指针后一位，这样b就保证慢指针后元素不重复
            nums[slow+1] = nums[fast];
            slow++;  // 慢指针向右继续移动；
        }
    }
    return slow + 1;
}

问题二： 给定一个带有头节点head的非空单链表，返回链表的中间节点，如果有两个中间节点，则返回第二个中间节点。
解法1: 哨兵法，如果哨兵节点中未定义长度，则需要遍历链表一次获取长度length，然后从头节点开始遍历length/2次，即可找到中间节点。

Node findMiddleNodeWithoutHead() {
    Node tmp = head.next;
    int length = 1;
    // 遍历链表获取长度    
    While(tmp.next != null) {
        tmp = tmp.next;
        length++;
    }    

    // 再遍历一次拿到链表中间节点
    tmp = head.next;
    Int middleLength = length/2;
    While(middleLength > 0) {
        tmp = tmp.next;
        middleLength—;
    }
    return tmp;
}

解法2: 快慢指针，上面方法效率不高，需要经过两次遍历链表。
主要分三步：
1、快慢指针同时指向head的后继节点
2、慢指针走一步，快指针走两步；
3、不断重复步骤2
当链表长度为奇数时，fast.next = null，slow为中间节点

当链表长度为偶数时，fast = null，slow是中间节点 当fast=null 或者 fast.next=null时，slow节点是中间节点

Node findMiddleNodeWithoutHead() {
    Node slow = head.next;
    Node fast = head.next;

    While(fast != null && fast.next != null) {
        // 快指针走2步
        Fast = fast.next.next;
        // 慢指针走1步
        Slow = slow.next;
    }
    Return slow;
}

问题三：输入一个链表，输出该链表中倒数第K个节点。只用一次遍历时间复杂度O(n)
还是用快慢指针法：
1、首先让快慢指针同时指向head后继节点；
2、快指针往前走K-1步，使快慢指针相隔K个节点，会先走到K节点；
3、快慢指针同时往前走一步，不断重复此步骤，知道快指针走到尾节点，此时的slow节点即是要找的倒序第K个节点

快慢步长指针

Node findReverseTailNode(int k) {
    Node slow = head.next;
    Node fast = head.next;

    // 快指针先到达第k节点
    Int tmpK = k - 1;
    While(tmpK > 0 && fast != null) {
        Fast = fast.next;
        tmpK—；
    }
    // 临界条件：k大于链表长度
    If (fast == null) {
        Return null;
    }
    // slow和fast同时前进，直到fast走到尾节点
    While(fast.next != null) {
        Slow = slow.next;
        Fast = fast.next;
    }
    Return slow;
}

问题四：判断链表是否有环，如果有，找到环的入口位置，要求空间复杂度O(1)

环链表

/**
 * 判断是否有环，返回快慢指针相遇节点，否则返回空指针
 */
Node detectCrossNode() {
    Node slow = head;
    Node fast = head;

    // 如果fast为空或fast.next为空说明不是链表环
    While(fast != null && fast.next != null) {
        Fast = fast.next.next;  // 快指针步长2
        Slow = slow.next;       // 慢指针步长1

        if（fast == null) {
            Return null;
        }

        If (fast == flow) {
            Return flow;
        }
    }

    Return null;
}

计算环链表
上图中7是快慢指针相遇的节点，可以看出慢指针走了L+S步，快指针除了走L+S步外，还额外在环里绕了n圈，所以快指针走了L+S+nR步(R是环的长度)，由于快指针的步长时慢指针的2倍，即2（L+S) = L+S+nR，即L+S = nR

综上所述，要找到入口节点，只需要定义两个指针，一个指针指向head，另一个指针指向快慢指针相遇节点，然后这两个指针不断遍历，当它们指向同一个节点时即是环的入口节点。

Node getRingEntryNode() {
    // 获取快慢指针相遇节点
    Node crossNode = detectCrossNode();

    // 如果没有相遇节点，则没有环
    if(crossNode == null) {
        Return null;
    }

    // 分别定义两个指针，一个指向head,一个指向相遇节点
    Node slowNode = head;
    Node fastNode = crossNode;

    While(fastNode.next != slowNode.next) {
        slowNode = slowNode.next;
        fastNode = fastNode.next;
    }
    Return slowNode;
}