首页 > 其他分享 >单链表题+数组题(快慢指针和左右指针)

单链表题+数组题(快慢指针和左右指针)

时间:2024-11-01 15:33:34浏览次数:3  
标签:表题 单链 int SingleLink next slow fast 指针

@

目录

说明:本文章用于 “单链表题+数组题”

“链表”知识

双指针技巧:分两类,一类是“快慢指针”,另一类是“左右指针”
“快慢指针”:-> 解决链表问题,判断链表是否包含环
“左右指针”:-> 解决数组(字符串)问题,比如二分搜索

快慢指针框架

Link method(Link head) {
	Link fast,slow;
	fast = slow = head;
	while (fast != null && fast.next != null) {
			//快指针每次前进两步
            fast = fast.next.next;
            //慢指针每次前进一步
            slow = slow.next;
	}
	return slow;
}

左右指针 - 二分搜索框架

一、案例说明(使用快慢指针)

单链表节点SingleLink

package algorithm;

import lombok.Data;

/**
 * 单链表节点
 */
@Data
public class SingleLink {
    int val;    //节点存储的值
    SingleLink next;    //指向下一个节点的指针

    public SingleLink(int val) {
        this.val = val;
        this.next = null;
    }

    public SingleLink(int val, SingleLink next) {
        this.val = val;
        this.next = next;
    }
}

main函数

public static void main(String[] args) {
        /** 有环
         * 1 -> 2 -> 3 -> 4
         *      ↑         ↓
         *      ↑    ←    ←
         */
        SingleLink link1 = new SingleLink(1);
        SingleLink link2 = new SingleLink(2);
        SingleLink link3 = new SingleLink(3);
        SingleLink link4 = new SingleLink(4);
        link1.next = link2;
        link2.next = link3;
        link3.next = link4;
        link4.next = link2;
        //偶数个数无环单链表  6-> 7 -> 8 -> 9
        SingleLink evenNumberLink = new SingleLink(6, new SingleLink(7, new SingleLink(8, new SingleLink(9, null))));
        //奇数个数无环单链表  6-> 7 -> 8 -> 9 -> 10
        SingleLink oddNumberLink = new SingleLink(6, new SingleLink(7, new SingleLink(8, new SingleLink(9, new SingleLink(10, null)))));
        
        //-----------------------------------双指针技巧套路框架------------------------------------------------------
        //-----------------------------------(使用快慢指针)------------------------------------------------------
        //问题1.1:判断链表是否有环
//        System.out.println("判断链表是否有环:" + hasCycle(link1));

        //问题1.2:已知链表有环,请返回这个环的起点位置
//        System.out.println("返回这个环的起点位置:" + detectCycle(link1).val);

        //问题1.3:寻找无环单链表的中点,要求:如果偶数个数以左面一个节点为中点
//        System.out.println("寻找偶数个数无环单链表的中点:" + returnMiddleLink(evenNumberLink).val);
//        System.out.println("寻找奇数个数无环单链表的中点:" + returnMiddleLink(oddNumberLink).val);

        //问题1.4:寻找无环单链表的中点,要求:如果偶数个数以右面一个节点为中点
//        System.out.println("寻找偶数个数无环单链表的中点:" + returnMiddleLink2(evenNumberLink).val);
//        System.out.println("寻找奇数个数无环单链表的中点:" + returnMiddleLink2(oddNumberLink).val);

        //问题1.5:寻找单链表的倒数第k个元素
//        System.out.println("寻找单链表的倒数第k个元素:" + reciprocalK(oddNumberLink, 2).val);

        //-----------------------------------(使用左右指针)------------------------------------------------------
        //问题2.1:(二分搜索)搜索数组中目标值的下标
//        System.out.println(":" + binarySearch(new int[]{1,2,3,4,5}, 4));

        //问题2.2:两数求和:输入一个升序排列的数组nums和一个目标值target,在nums中找到两个数相加=target,请返回这两个数的索引
//        twoSum(new int[]{1, 2, 3, 4, 5}, 6);
//        for (int[] arr : resList) {
//            for (int item : arr) {
//                System.out.print(" " + item);
//            }
//            System.out.println();
//        }

        //问题2.3:反转数组,熟悉reverse方法的内部实现
//        int[] arr = new int[]{1,2,3,4,5};
//        reverse(arr);
//        Arrays.stream(arr).forEach(item -> System.out.print(" " + item));
    }

问题1.1判断链表是否有环

//问题1.1:判断链表是否有环
    public static boolean hasCycle(SingleLink head) {
        SingleLink fast, slow;
        //初始化快、慢指针指向头节点
        fast = slow = head;
        while (fast != null && fast.next != null) {
            //快指针每次前进两步
            fast = fast.next.next;
            //慢指针每次前进一步
            slow = slow.next;
            //如果存在环,快、慢指针必然相遇
            if (fast == slow) return true;
        }
        return false;
    }

问题1.2:已知链表有环,请返回这个环的起点位置

思路讲解

/*问题1.2:已知链表有环,请返回这个环的起点位置
     *  思路:快慢指针相遇时,将快慢指针中任意一个重新指向head,然后两个指针同速前进,k-m步后就会相遇,相遇之处就是环的起点
     */
    public static SingleLink detectCycle(SingleLink head) {
        SingleLink fast, slow;
        //初始化快、慢指针指向头节点
        fast = slow = head;
        while (fast != null && fast.next != null) {
            //快指针每次前进两步
            fast = fast.next.next;
            //慢指针每次前进一步
            slow = slow.next;
            //如果存在环,快、慢指针必然相遇
            if (fast == slow) break;
        }
        //先把一个指针重新指向head
        slow = head;
        while (slow != fast) {
            //两个指针以相同的速度前进
            fast = fast.next;
            slow = slow.next;
        }
        //两个指针相遇的那个单链表节点就是环的起点
        return slow;
    }

问题1.3:寻找无环单链表的中点,要求:如果偶数个数以左面一个节点为中点

//问题1.3:寻找无环单链表的中点,要求:如果偶数个数以左面一个节点为中点
    public static SingleLink returnMiddleLink(SingleLink head) {
        SingleLink fast, slow;
        //初始化快、慢指针指向头节点
        fast = slow = head;
        while (fast != null && fast.next != null && fast.next.next != null) {
            //快指针每次前进两步
            fast = fast.next.next;
            //慢指针每次前进一步
            slow = slow.next;
        }
        return slow;
    }

问题1.4:寻找无环单链表的中点,要求:如果偶数个数以右面一个节点为中点

//问题1.4:寻找无环单链表的中点,要求:如果偶数个数以右面一个节点为中点
    public static SingleLink returnMiddleLink2(SingleLink head) {
        SingleLink fast, slow;
        //初始化快、慢指针指向头节点
        fast = slow = head;
        while (fast != null && fast.next != null) {
            //快指针每次前进两步
            fast = fast.next.next;
            //慢指针每次前进一步
            slow = slow.next;
        }
        return slow;
    }

问题1.5:寻找单链表的倒数第k个元素

	/**
     * 问题1.5:寻找单链表的倒数第k个元素
     *  思路:使用快慢指针,让快指针先走k步,然后快慢指针同速前进,当快指针走到末尾null时,慢指针所在位置就是倒数第k个链表节点
     * @param head 头链表节点
     * @param k 倒数第k个数
     * @return 节点
     */
    public static SingleLink reciprocalK(SingleLink head, int k) {
        SingleLink fast, slow;
        fast = slow = head;
        while (k-- > 0) fast = fast.next;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

二、案例说明(使用左右指针)

问题2.1:(二分搜索)搜索数组中目标值的下标

//问题2.1:(二分搜索)搜索数组中目标值的下标
    public static int binarySearch(int[] nums, int target) {
        //左右指针在数组的两端初始化
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        return -1;
    }

问题2.2:两数求和:输入一个升序排列的数组nums和一个目标值target,在nums中找到两个数相加=target,请返回这两个数的索引

//问题2.2:两数求和:输入一个升序排列的数组nums和一个目标值target,在nums中找到两个数相加=target,请返回这两个数的索引
    public static void twoSum(int[] nums, int target) {
        //左右指针在数组的两端初始化
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                resList.add(new int[]{left, right});
                right--;
                continue;
            } else if (sum < target) {
                left++;    //让sum大一点
            } else if (sum > target) {
                right--;  //让sum小一点
            }
        }
    }

问题2.3:反转数组,熟悉reverse方法的内部实现

//问题2.3:反转数组,熟悉reverse方法的内部实现
    public static void reverse(int[] nums) {
        //左右指针在数组的两端初始化
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            //交换nums[left]和nums[right]
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }

本人其他文章链接

1.单链表题+数组题(快慢指针和左右指针)

2.BFS(Breath First Search 广度优先搜索)

3.”回溯算法“框架及练习题

4.JAVA 二叉树面试题

标签:表题,单链,int,SingleLink,next,slow,fast,指针
From: https://www.cnblogs.com/bigcat26/p/18520358

相关文章

  • C语言中指针和数组的相互关系
    在C语言中,指针和数组有着紧密的相互关系。数组是数据的集合,而指针则是一个包含内存地址的变量。指针可以用来访问数组的元素,便于高效的内存访问和操作。更具体来说,数组名本身就是一个指向首元素的指针、通过指针运算,我们可以遍历数组的每个元素、数组和指针的索引操作是等价的、......
  • 智能指针使用
    普通指针的不足new和new[]的内存需要用delete和deletel]释放。程序员的主观失误,忘了或漏了释放。程序员也不确定何时释放。普通指针的释放类内的指针,在析构函数中释放。C++内置数据类型,如何释放?new出来的类,本身如何释放?C++11新增三个智能指针类型unique_pt......
  • 【C++】智能指针的正确使用方式
    本文将从这几方面讲解智能指针:智能指针的应用场景分析智能指针的性能分析:为什么shared_ptr性能比unique_ptr差指针作为函数参数时应该传,传值、传引用,还是裸指针?对于智能指针的使用,实际上是对所有权和生命周期的思考1.unique_ptr:专属所有权1.1unique_ptr介绍我们大......
  • 什么是指针数组 和 数组指针
    什么是指针数组答:就是一个数组,里面存的是指针而已它的写法可以如下:int*a[10];看看,它就是一个指针数组,数组名字当然是a,里面有10个元素,每个元素都是一个int*类型(即存放整型地址的指针)的指针。我们可以这样用,比如: #include<stdio.h>Cintmain(){intx=10,y=20,z=3......
  • C/C++中的指针详解(重点)
    指针是C和C++中一个重要且强大的特性。它们允许程序员直接访问和操作内存,提供了灵活的内存管理和高效的数据结构实现。对一个变量取*操作其实就是取到这个变量的地址,然后再对取到的变量进行读写等操作以下是对指针的详细介绍:1.什么是指针指针是一个变量,它存储另一个变量的......
  • 指针--结构体指针
    结构体:新的类型(由任意若干个基本类型组成)a1,a2,a3是AA这个结构体类型的个体,每个个体都有AA这个结构体里面的两个部件嵌套调用,结构体嵌套数组里的元素就是结构体child类型的数据x4是结构体AA类型的,a1,a2,a3也是结构体AA类型的,同一类型可以相等只看变量声名的时候是无法判......
  • C++——写一函数,将一个3x3的整型矩阵转置。用指针或引用方法处理。
    没注释的源代码#include<iostream>usingnamespacestd;voidmove(int*p);intmain(){  inta[3][3],*p;  cout<<"pleaseinputmatrix:"<<endl;  for(inti=0;i<3;i++)  {    for(intj=0;j<3;j++)    {     ......
  • C++——将一个5x5的矩阵中最大的元素放在中心,4个角分别放4个最小的元素(按从左到右、
    没注释的源代码#include<iostream>#include<stdio.h>#include<string.h>usingnamespacestd;voidtransform(int*arry,intcol_row);intmain(){   intarry[5][5];   cout<<"Pleaseentera5x5matrix:"<<endl;   for(......
  • Go语言内置集合的隐式指针
    在Go语言中,有几种内置集合类型(如slice、map和channel),这些类型的特殊之处在于它们实际上是隐式指针。这意味着当我们将这些集合类型传递给函数或方法时,传递的是它们的引用,而不是拷贝。这种特性使得这些集合能够在函数中直接修改原始数据,而不需要显式传递指针。1.内置集合......
  • 单链表题带刷(二)
    目录一、链表的回文结构1.1题目1.2解题思路二、相交链表2.1题目一、链表的回文结构1.1题目https://www.nowcoder.com/share/jump/6870342311730273670970https://www.nowcoder.com/share/jump/68703423117302736709701.2解题思路思路一:创建新链表,将原链表反......