阿里面试算法题四

时间:2021-7-3 作者:qvyue

最长不含有重复串的字符串

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

// 思路是使用 hashmap 进行存储,之前的位置
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }
        HashMap map = new HashMap();
        int max = 1;
        int left = 0;
        for(int i=0;i 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 countSmaller(int[] nums) {
        List res = new ArrayList();
        if(nums == null || nums.length == 0){
            return res;
        }
        List list = new ArrayList();
        for(int i = nums.length -1;i >= 0;i--){
            int left = 0, right = list.size();
            while(left = 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 findDuplicates(int[] nums) {
        List 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 

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] 

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=0;i--){
            min = Math.min(A[i],min);
            rightMin[i] = min;
        }

        for(int i=0;i

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 spiralOrder(int[][] matrix) {
        List 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 = 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 

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 

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 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>i) & 1);
            }
            res |= (sum % 3) 

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

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 list = new ArrayList();
        list.add(1);
        // 这里采用,每一个数,2,3,5 都采用一个指针维护和上一个数的关系
        int s1 = 0, s2 = 0, s3 = 0;
        while(list.size() 

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 deque = new LinkedList();
        int[] res = new int[nums.length - k + 1];
        for(int j=0,i = 1 - k;j 0 && deque.peekFirst() == nums[i-1]) deque.removeFirst();
            while(!deque.isEmpty() && deque.peekLast() = 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[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

392. 判断子序列

给定字符串 s 和 t ,判断 s 是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度

字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,”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

1. 两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

 public int[] twoSum(int[] nums, int target) {
        HashMap map = new HashMap();
        for(int i=0;i

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[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> threeSum(int[] nums) {
       Set> 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[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 map = new HashMap();
        for(int i=0;i= left){
                maxLen = Math.max(maxLen,i-left);
                left = j;
                }
            }
            map.put(c,i+1);
        }
        return Math.max(maxLen,s.length()-left);
    }

插入括号

有长度为length(0i同一个位置只能插入一个括号,求使得括号序列合法的最小代价,并给出解法的时间复杂度和空间复杂度。
例如输入

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 

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 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 
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。