阿里面试算法题四
2020-07-12 本文已影响0人
Tim在路上
最长不含有重复串的字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
// 思路是使用 hashmap 进行存储，之前的位置
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() == 0){
return 0;
}
HashMap<Character,Integer> map = new HashMap<>();
int max = 1;
int left = 0;
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(map.containsKey(c) && map.get(c) > left){
max = Math.max(i-left,max);
left = map.get(c);
}
map.put(c,i+1);
}
return Math.max(s.length()-left,max);
}
315. 计算右侧小于当前元素的个数
给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例:
输入: [5,2,6,1]
输出: [2,1,1,0]
// 计算右侧小于当前元素的个数，
// 可以从右边开始进行而进制的插入排序，插入的位置就是
public List<Integer> countSmaller(int[] nums) {
List<Integer> res = new ArrayList<>();
if(nums == null || nums.length == 0){
return res;
}
List<Integer> list = new ArrayList<>();
for(int i = nums.length -1;i >= 0;i--){
int left = 0, right = list.size();
while(left < right){
int mid = left + (right - left)/2;
if(list.get(mid) >= nums[i]){
right = mid;
}else{
left = mid + 1;
}
}
list.add(left, nums[i]);
res.add(left);
}
Collections.reverse(res);
return res;
}
442. 数组中的重复数据
给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
示例：
输入:
[4,3,2,7,8,2,3,1]
输出:
[2,3]
// 这里因为 数值都是 1~n 可以将其散列在长度为n的数组中
public List<Integer> findDuplicates(int[] nums) {
List<Integer> res = new ArrayList<>();
if(nums == null || nums.length == 0){
return res;
}
int n = nums.length;
// 可以将字符的添加增加到遍历中
for(int x: nums){
int index = Math.abs(x) - 1;
nums[index] = -nums[index];
if(nums[index] > 0){
res.add(Math.abs(x));
}
}
return res;
}
189. 旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
// 将数组进行三次反转
public void rotate(int[] nums, int k) {
int n = nums.length;
k = k % n;
reserve(nums,0,nums.length-k-1);
reserve(nums,nums.length-k,nums.length-1);
reserve(nums,0,nums.length-1);
}
public void reserve(int[] nums, int left, int right){
while(left < right){
swap(nums,left,right);
left++;
right--;
}
}
public void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
31. 下一次排列
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
public void nextPermutation(int[] nums) {
nextPermutation(nums,0,nums.length);
}
private void nextPermutation(int[] nums, int start, int end) {
int p = end -2;
while (p > -1 && nums[p] >= nums[p+1]){
p--;
}
if (p == -1){
reverse(nums,0,end);
return;
}
int c = end - 1;
while (c > p && nums[c] <= nums[p]){
c--;
}
swap(nums,p,c);
reverse(nums,p+1,end);
return;
}
private void swap(int[] nums, int p, int c) {
int tmp = nums[c];
nums[c] = nums[p];
nums[p] = tmp;
}
private void reverse(int[] nums, int start, int end) {
for (int i = 0;i<(end - start)/2;i++){
int tmp = nums[start + i];
nums[start + i] = nums[end - i -1];
nums[end - i - 1] = tmp;
}
915. 分割数组
给定一个数组 A，将其划分为两个不相交（没有公共元素）的连续子数组 left 和 right， 使得：
left 中的每个元素都小于或等于 right 中的每个元素。
left 和 right 都是非空的。
left 要尽可能小。
在完成这样的分组后返回 left 的长度。可以保证存在这样的划分方法。
示例 1：
输入：[5,0,3,8,6]
输出：3
解释：left = [5,0,3]，right = [8,6]
// 因为数组的顺序是不能够改变的，所以思路是采用两个数组，将从左到右，从右到左的小数组
public int partitionDisjoint(int[] A) {
if(A == null || A.length == 0){
return 0;
}
int[] leftMax = new int[A.length];
int[] rightMin = new int[A.length];
int max = A[0];
for(int i=0;i<A.length;i++){
max = Math.max(A[i], max);
leftMax[i] = max;
}
int min = A[A.length-1];
for(int i=A.length-1;i>=0;i--){
min = Math.min(A[i],min);
rightMin[i] = min;
}
for(int i=0;i<A.length-1;i++){
if(leftMax[i] <= rightMin[i+1]){
return i+1;
}
}
return -1;
}
54. 矩阵旋转
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
// 思路是，定义左上角和右下角位置，每次进行缩减, 只需要多住一个一个情况柱状模式
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return res;
}
int leftUpRow = 0, leftUpCol = 0;
int rightDownRow = matrix.length -1, rightDownCol = matrix[0].length - 1;
int r = 0, c = 0;
while(leftUpRow <= rightDownRow && leftUpCol <= rightDownCol){
r = leftUpRow;
c = leftUpCol;
while(c <= rightDownCol){
res.add(matrix[leftUpRow][c]);
c++;
}
c--;
r++;
while(r <= rightDownRow){
res.add(matrix[r][rightDownCol]);
r++;
}
r--;
c--;
while(c >= leftUpCol && leftUpRow != rightDownRow){
res.add(matrix[rightDownRow][c]);
c--;
}
c++;
r--;
while(r > leftUpRow && leftUpCol != rightDownCol){
res.add(matrix[r][leftUpCol]);
r--;
}
leftUpCol++;
leftUpRow++;
rightDownCol--;
rightDownRow--;
}
return res;
}
53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
// 使用dp
public int maxSubArray(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int maxSum = Integer.MIN_VALUE;
int curSum = 0;
for(int x : nums){
if(curSum < 0){
curSum = x;
}else{
curSum += x;
}
maxSum = Math.max(curSum, maxSum);
}
return maxSum;
}
152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
// dp , 同时记录最大和最小，当前值为负数是交换
public int maxProduct(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int max = 1;
int min = 1;
int maxProduct = Integer.MIN_VALUE;
for(int x : nums){
if(x < 0){
int tmp = min;
min = max;
max = tmp;
}
min = Math.min(min * x,x);
max = Math.max(max * x,x);
maxProduct = Math.max(maxProduct,max);
}
return maxProduct;
}
138.复制带有随机指针的链表
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
// 复制带有随机指针的链表
// 使用hashmap 进行复制节点，同时按照链表顺序间next和随机节点连接起来
public Node copyRandomList(Node head) {
if(head == null){
return head;
}
HashMap<Node, Node> map = new HashMap<>();
Node p = head;
while(p != null){
map.put(p, new Node(p.val));
p = p.next;
}
p = head;
while(p != null){
map.get(p).next = map.get(p.next);
map.get(p).random = map.get(p.random);
p = p.next;
}
return map.get(head);
}
136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
// 异或将相同的数约掉
public int singleNumber(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int res = 0;
for(int x: nums){
res ^= x;
}
return res;
}
137. 只出现一次的数字2
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2]
输出: 3
n 个 数 1 个 数，做加法，然后将数移到具体位置取模，不进位
// 可以采用三进制加法，将数的每一位做，不进位的加法
public int singleNumber(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int res = 0;
for(int i=0;i<32;i++){
int sum = 0;
for(int j=0;j<nums.length;j++){
sum += ((nums[j]>>i) & 1);
}
res |= (sum % 3) << i;
}
return res;
}
260. 只出现一次的数字3
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]
public int[] singleNumber(int[] nums) {
// 两个数字出现，思路所有数字一起异或，就只剩下两个数字的异或，
// res 与 相反数相与
int res = 0;
for(int x : nums){
res ^= x;
}
// 获得差异，只会保留位中出现最右边的第一个1，这个1 要么是来自x, 要么来自y
int diff = res & -res;
int x = 0;
for(int i=0;i<nums.length;i++){
if((diff & nums[i]) != 0){
x = x ^ nums[i];
}
}
return new int[]{x,res^x};
}
263. 丑数
编写一个程序判断给定的数是否为丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例 1:
输入: 6
输出: true
解释: 6 = 2 × 3
// 让 2，3，5
public boolean isUgly(int num) {
if(num == 0){
return false;
}
if(num == 1){
return true;
}
if(num % 2 == 0){
return isUgly(num/2);
}
if(num % 3 == 0){
return isUgly(num/3);
}
if(num % 5 == 0){
return isUgly(num/5);
}
return false;
}
264. 丑数2
编写一个程序，找出第 n 个丑数。
丑数就是质因数只包含 2, 3, 5 的正整数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
// 依次进行2，3，5 找n个丑数
public int nthUglyNumber(int n) {
if(n == 1){
return 1;
}
List<Integer> list = new ArrayList<>();
list.add(1);
// 这里采用，每一个数，2，3，5 都采用一个指针维护和上一个数的关系
int s1 = 0, s2 = 0, s3 = 0;
while(list.size() < n){
int m1 = list.get(s1) * 2;
int m2 = list.get(s2) * 3;
int m3 = list.get(s3) * 5;
int min = Math.min(m1, Math.min(m2, m3));
list.add(min);
if(min == m1){
s1++;
}
if(min == m2){
s2 ++;
}
if(min == m3){
s3 ++;
}
}
return list.get(list.size()-1);
}
59. 滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
// 思路是： 维护一个双端队列，如果，队列头等于 数组第一个元素，当组数大于0 弹出
// 队列为中元素小于当前元素时弹出，让队列中只维护大于改元素的元素
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums == null || nums.length == 0 || k == 0){
return new int[0];
}
Deque<Integer> deque = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
for(int j=0,i = 1 - k;j<nums.length;i++,j++){
if(i > 0 && deque.peekFirst() == nums[i-1]) deque.removeFirst();
while(!deque.isEmpty() && deque.peekLast() < nums[j]) deque.removeLast();
deque.addLast(nums[j]);
if(i >= 0) res[i] = deque.peekFirst();
}
return res;
}
128. 最长连续子序列
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
思路是按顺序进行统计，跳过相等的数
// 使用hashmap 进行每一个数的统计
public int longestConsecutive(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
Arrays.sort(nums);
int max = 1;
for(int i =0;i<nums.length;i++){
int curMax = 1;
while(i+1 < nums.length && nums[i] + 1 >= nums[i+1]){
if(nums[i] + 1 == nums[i+1]) curMax++;
i++;
}
max = Math.max(max, curMax);
}
return max;
}
169. 多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
// 超过半数的元素，统计个数，相同相加，不同相减
public int majorityElement(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int count = 1;
int pre = nums[0];
for(int i=1;i<nums.length;i++){
if(pre == nums[i]){
count ++;
}else if(count == 0){
count = 1;
pre = nums[i];
}else{
count --;
}
}
return pre;
}
392. 判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1:
s = "abc", t = "ahbgdc"
返回 true.
示例 2:
s = "axc", t = "ahbgdc"
返回 false.
// 判断子序列
public boolean isSubsequence(String s, String t) {
if(t == null || s.length() > t.length()){
return false;
}
int j = -1;
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
j = t.indexOf(c,j+1);
if(j == -1){
return false;
}
}
return true;
}
1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
int diff = target - nums[i];
if(map.containsKey(diff)){
int j = map.get(diff);
return new int[]{j, i};
}
map.put(nums[i],i);
}
return new int[]{-1, -1};
}
153. 寻找旋转排序数组中的最小值
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]
输出: 1
// 直接使用二分查询进行查找
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
// 考虑不旋转的情况,考虑只有一个元素的情况
if(nums[0] <= nums[nums.length-1]){
return nums[0];
}
while(left < right){
int mid = left + (right - left)/2;
// 如果只有两个元素，那么mid元素可能就是第一个元素
if(nums[mid] >= nums[0]){
left = mid + 1;
}else{
right = mid;
}
}
return nums[left];
}
15. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
// 三数之和
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> res = new LinkedHashSet<>();
if(nums == null || nums.length == 0){
return new ArrayList<>(res);
}
// 使用夹击的策略
Arrays.sort(nums);
// 使用hashmap
int left = 0, right = nums.length - 1;
for(int i=0;i<nums.length-2;i++){
left = i + 1;
right = nums.length-1;
while(left < right){
int sum = nums[left] + nums[right];
if(sum == -nums[i]){
res.add(Arrays.asList(nums[i],nums[left],nums[right]));
}
if(sum >= -nums[i]){
right--;
}else{
left++;
}
}
}
return new ArrayList<>(res);
}
3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
// 使用hashmap 位置每一个字符的位置，方便查询是否重复
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() == 0){
return 0;
}
int maxLen = 1;
int left = 0;
HashMap<Character, Integer> map = new HashMap<>();
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(map.containsKey(c)){
int j = map.get(c);
if(j >= left){
maxLen = Math.max(maxLen,i-left);
left = j;
}
}
map.put(c,i+1);
}
return Math.max(maxLen,s.length()-left);
}
插入括号
有长度为length（0<length≤100000)的一个括号序列sequence，只有“（”或者“）”两种字符，每个括号的左右两边都能插一个括号，总共有length+1个位置可以插入括号，在第i个位置插入任意括号的代价是costi同一个位置只能插入一个括号，求使得括号序列合法的最小代价，并给出解法的时间复杂度和空间复杂度。
例如输入
length=6,sequence="()))((",cost=[1,2,5,5,3,4,1],输出8.
思路是，遇到（ 左括号压入栈，遇到右括号弹出栈，如果栈为空说明在当前位置前缺少左括号，然后找向前一个最小的数，并标记
如果当前位置
92. 反转链表
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
思路，总共是两步，找到前驱和后记，以及要反转的的头和尾节点，同时将尾部断开，把器转化为普通结点进行旋转
// 主要分为两步，找到前驱节点，以及首节点使用， n 来控制尾节点
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head == null){
return null;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
ListNode end = dummy;
while(n-- > 0 && end != null){
end = end.next;
}
while(m-- > 1 && pre != null){
pre = pre.next;
}
ListNode start = pre.next;
ListNode next = end.next;
end.next = null;
pre.next = reverse(start);
start.next = next;
return dummy.next;
}
public ListNode reverse(ListNode head){
if(head == null){
return head;
}
ListNode pre = null, p = head;
while(p != null){
ListNode next = p.next;
p.next = pre;
pre = p ;
p = next;
}
return pre;
}
86. 分割链表
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
// 思路是，将小于该元素的删除，并记录，再次遍历插入
// 看懂题目，是小于X 的节点放在前面，可以将其拆分为两个队列进行合并
public ListNode partition(ListNode head, int x) {
ListNode left = new ListNode(-1);
ListNode right = new ListNode(-1);
ListNode cur = head, p = left, q = right;
while(cur != null){
if(cur.val < x){
p.next = new ListNode(cur.val);
p = p.next;
}else {
q.next = new ListNode(cur.val);
q = q.next;
}
cur = cur.next;
}
p.next = right.next;
return left.next;
}
83. 使用递归删除重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
// 使用递归删除重复元素
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null){
return head;
}
if(head != null && head.next != null && head.val == head.next.val){
return deleteDuplicates(head.next);
}else{
head.next = deleteDuplicates(head.next);
return head;
}
}
82. 删除链表中重复元素2
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
// 使用递归删除
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null){
return head;
}
if(head != null && head.next != null && head.val == head.next.val){
// 这里进行迭代找的新的节点
ListNode p = head.next;
for(;p != null && p.val == head.val; p = p.next);
return deleteDuplicates(p);
}else{
head.next = deleteDuplicates(head.next);
return head;
}
}
237. 删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
现有一个链表 -- head = [4,5,1,9]，它可以表示为:
示例 1:
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
// 思路很简单，就是讲当前节点和下一个节点互换，跳过下一个节点
public void deleteNode(ListNode node) {
if(node != null && node.next != null){
node.val = node.next.val;
}
node.next = node.next.next;
}
```
#### 19. 删除链表的倒数第n个节点
```
// 思路， 倒数第n个节点
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head == null){
return head;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode fast = dummy, slow = dummy;
while(n-- > 0){
fast = fast.next;
}
while(fast != null && fast.next != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
```
#### 203. 删除链表中等于给定值的所有节点
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
```
// 删除链表中等于给定值的所有节点，可以使用递归
public ListNode removeElements(ListNode head, int val) {
if(head == null){
return head;
}
if(head.val == val){
return removeElements(head.next, val);
}else{
head.next = removeElements(head.next,val);
return head;
}
}
```
#### 61. 旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
注意k 为0 不进行旋转，和 k 取余为0 也是不旋转的的情况
```
// 旋转链表
// 思路将其断开，然后再拼接
public ListNode rotateRight(ListNode head, int k) {
if(head == null || head.next == null){
return head;
}
ListNode p = head;
int len = 0;
while(p != null){
len ++;
p = p.next;
}
k = k % len;
if(k == 0){
return head;
}
// 快慢指针
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode fast = dummy, slow = dummy;
while(k-- > 0){
fast = fast.next;
}
while(fast != null && fast.next != null){
fast = fast.next;
slow = slow.next;
}
ListNode first = slow.next;
slow.next = null;
if(fast != null){
fast.next = head;
}
return first;
}
```
#### 2. 两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
```
// 两数相加，实质是链表的合并
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode cur = new ListNode(-1);
ListNode p = l1, q = l2,r = cur;
int c = 0;
while(p != null || q != null || c != 0){
int x = p != null ? p.val : 0;
int y = q != null ? q.val : 0;
int num = x + y + c;
r.next = new ListNode(num % 10);
c = num / 10;
r = r.next;
p = p != null ? p.next:null;
q = q != null ? q.next:null;
}
return cur.next;
}
```
#### 445. 两数相加
```
// 要想递归，两个链表要同样的长度才行
// 反转相加，效率高
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode p = reverse(l1);
ListNode q = reverse(l2);
ListNode head = new ListNode(-1);
ListNode cur = head;
int c = 0;
while(p != null || q != null || c != 0){
int x = p != null ? p.val : 0;
int y = q != null ? q.val : 0;
int num = x + y + c;
cur.next = new ListNode(num % 10);
c = num / 10;
cur = cur.next;
p = p != null ? p.next : null;
q = q != null ? q.next : null;
}
return reverse(head.next);
}
public ListNode reverse(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode next = reverse(head.next);
head.next.next = head;
head.next = null;
return next;
}
```
```
// 链表两数相加思路： 首先计算两个链表的长度，然后在短的前面补0，然后递归相加，注意在进行递归时创建好链表的节点，
// 回溯时添加值，并判断返回的上一个节点是否大于 10 ，最终大于10 再添加个节点
// 可不可以使用回溯进行两数相加
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int l1Size = listSize(l1);
int l2Size = listSize(l2);
if (l1Size - l2Size > 0) {
l2 = headFillZero(l2, l1Size - l2Size);
} else {
l1 = headFillZero(l1, l2Size - l1Size);
}
ListNode node = addTwoNumbers(l1, l2, new ListNode(-1));
if (node.val >= 10) {
ListNode newNode = new ListNode(node.val % 10);
node.val = node.val / 10;
newNode.next = node.next;
node.next = newNode;
}
return node;
}
public static ListNode addTwoNumbers(ListNode l1, ListNode l2, ListNode head) {
if (l1.next == null && l2.next == null) {//遇见l1和l2的最后两个节点，相加返回
head.next = new ListNode(l1.val + l2.val);
return head.next;
}
head.next = new ListNode(-1);//先构建好一个节点追加在head后面，具体val在递归返回阶段依次计算填充.
head = head.next;
ListNode node = addTwoNumbers(l1.next == null ? l1 : l1.next, l2.next == null ? l2 : l2.next, head);
int temp = l1.val + l2.val + node.val / 10;//计算当前节点的值，node.val是上一个节点的值，如果node.val大于10，则进位计算.
node.val = node.val % 10;//重新计算上一个节点的值.
head.val = temp;
return head;
}
public static int listSize(ListNode listNode) {
if (listNode == null) {
return 0;
}
int size = 0;
while (listNode != null) {
size++;
listNode = listNode.next;
}
return size;
}
public static ListNode headFillZero(ListNode node, int fillNum) {
if (fillNum == 0) {
return node;
}
ListNode head = node;
for (int i = 0; i < fillNum; i++) {
ListNode temp = head;
head = new ListNode(0);
head.next = temp;
}
return head;
}
```
#### 234. 回文链表
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
使用回溯判断回文链表
```
// 使用回溯进行判断, 保存首节点
ListNode first = null;
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null){
return true;
}
first = head;
return isPalindromeCore(head);
}
public boolean isPalindromeCore(ListNode head){
if(head == null){
return true;
}
if(!isPalindromeCore(head.next)) return false;
if(first.val != head.val) return false;
first = first.next;
return true;
}
```
#### 24. 两两交换链表中的节点
定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
```
// 进行递归
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode first = head, second = head.next;
ListNode next = swapPairs(second.next);
second.next = first;
first.next = next;
return second;
}
```
#### 160. 橡胶链表的判断
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
```
// 找到相交节点的首节点， 思路将其两个进行拼接，遍历第一个相同的节点
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p = headA, q = headB;
while(p != q){
p = p == null ? headB : p.next;
q = q == null ? headA : q.next;
}
return p;
}
```
#### 141. 快慢指针判断是否有环
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
```
// 快慢指针进行判断
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null){
return false;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode fast = dummy, slow = dummy;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
break;
}
}
if(fast == null || fast.next == null){
return false;
}
return true;
}
```
#### 142. 环形链表2
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表
```
// 从相交节点走到 第一个节点 和 从起始节点走到第一个节点距离一样
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null){
return null;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
// 注意从dummy 开始，在进行查找第一个节点的时候也得从dummy 开始
ListNode fast = dummy, slow = dummy;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(slow == fast){
break;
}
}
if(fast == null || fast.next == null){
return null;
}
fast = dummy;
while(fast.val != slow.val){
fast = fast.next;
slow = slow.next;
}
return slow;
}
```
#### 21. 合并两个排序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
21.合并两个有序的链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
// 合并链表
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(-1);
ListNode cur = head;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
cur.next = new ListNode(l1.val);
l1 = l1.next;
}else{
cur.next = new ListNode(l2.val);
l2 = l2.next;
}
cur = cur.next;
}
if(l1 != null){
cur.next = l1;
}
if(l2 != null){
cur.next = l2;
}
return head.next;
}
