单链表的头指针和头结点

文章目录 说明：本文章用于 “单链表题+数组题”“链表”知识一、案例说明（使用快慢指针）问题1.1判断链表是否有环问题1.2：已知链表有环，请返回这个环的起点位置问题1.3：寻找无环单链表的中点，要求：如果偶数个数以左面一个节点为中点问题1.4：寻找无环单链表的中点，要求：如果偶数个数以右面一个节点为中点问题1.5：寻找单链表的倒数第k个元素 二、案例说明（使用左右指针）问题2.1：（二分搜索）搜索数组中目标值的下标问题2.2：两数求和：输入一个升序排列的数组nums和一个目标值target，在nums中找到两个数相加=target，请返回这两个数的索引问题2.3：反转数组，熟悉reverse方法的内部实现

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

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

快慢指针框架：

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;/** * 单链表节点 */@Datapublic 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--; //让sumkkdgz点 } } } 问题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--; } }