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

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

@[TOC]

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

“链表”知识

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

==快慢指针框架==:

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

==左右指针 - 二分搜索框架==:
image.png

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

==单链表节点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:已知链表有环,请返回这个环的起点位置

==思路讲解==:
image.png
image.png

/*问题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 二叉树面试题

目录
相关文章
|
25天前
使用指针访问数组元素
【10月更文挑战第30天】使用指针访问数组元素。
32 3
|
24天前
使用指针访问数组元素
【10月更文挑战第31天】使用指针访问数组元素。
32 2
|
2月前
|
存储
如何使用指针数组来实现动态二维数组
指针数组可以用来实现动态二维数组。首先,定义一个指向指针的指针变量,并使用 `malloc` 为它分配内存,然后为每个子数组分配内存。通过这种方式,可以灵活地创建和管理不同大小的二维数组。
|
2月前
|
存储
如何通过指针数组来实现二维数组?
介绍了二维数组和指针数组的概念及其区别,详细讲解了如何使用指针数组模拟二维数组,包括定义与分配内存、访问和赋值元素、以及正确释放内存的步骤,适用于需要动态处理二维数据的场景。
|
2月前
|
存储 算法 C语言
C语言:什么是指针数组,它有什么用
指针数组是C语言中一种特殊的数据结构,每个元素都是一个指针。它用于存储多个内存地址,方便对多个变量或数组进行操作,常用于字符串处理、动态内存分配等场景。
|
2月前
魔法指针 之 二级指针 指针数组
魔法指针 之 二级指针 指针数组
19 1
|
2月前
|
存储
一篇文章了解区分指针数组,数组指针,函数指针,链表。
一篇文章了解区分指针数组,数组指针,函数指针,链表。
19 0
|
2月前
|
编译器 C语言
【C语言】指针篇-深入探索数组名和指针数组- 必读指南(2/5)
【C语言】指针篇-深入探索数组名和指针数组- 必读指南(2/5)
|
4月前
|
搜索推荐 C语言
指针与数组
指针与数组
59 9
|
2月前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表,并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现,以及一个示例程序来演示这些操作。
29 0