美文网首页
快慢指针的算法应用

快慢指针的算法应用

作者: Arthurcsh | 来源:发表于2020-04-22 00:29 被阅读0次
    数据结构

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

    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;
    }
    

    相关文章

      网友评论

          本文标题:快慢指针的算法应用

          本文链接:https://www.haomeiwen.com/subject/vfpvihtx.html