第一页总结

链表

反转

206. 反转链表

206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

递归思路：
每一个子递归都将当前节点下一个节点的下一个节点指向当前节点，当前节点的下一个节点置空。 递归终止条件：head为空或head.next为空。

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。
• 空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next=null;
        return newHead;
    }
}

迭代思路：用pre和cur两个指针遍历链表
复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度，需要遍历链表一次。
• 空间复杂度：O(1)

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

25. K 个一组翻转链表

25. K 个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

递归思路：k个一组翻转链表，对于每一组来说就是反转前n。所以可以采用递归的思想，首先找到下一个要翻转前n的节点，再翻转当前head的前n个节点，最后递归的反转后续链表并连接起来。

时间复杂度分析：
复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode p = head;
        // 找到下一个要反转前n的head
        for(int i=0;i<k;i++){
            if(p==null){
                return head;
            }
            p=p.next;
        }
        // 反转前N
        ListNode newHead = reverseN(head,k);
        head.next = reverseKGroup(p,k);
        return newHead;
    }

    /**
        反转前N
     */
    ListNode successor = null;
    private ListNode reverseN(ListNode head, int n){
        // 找到第一个不用反转的节点
        if(n==1){
            successor = head.next;
            return head;
        }
        ListNode newHead = reverseN(head.next, n-1);
        head.next.next = head;
        head.next = successor;
        return newHead;
    }
}

迭代：
时间复杂度：O(n)，其中 n 为链表的长度。head 指针会在 O(⌊n/k⌋)个节点上停留，每次停留需要进行一次 O(k)的翻转操作。
空间复杂度：O(1).

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode hair = new ListNode(0);
        hair.next = head;
        ListNode pre = hair;

        while (head != null) {
            ListNode tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail.next;
                if (tail == null) {
                    return hair.next;
                }
            }
            ListNode nex = tail.next;
            ListNode[] reverse = myReverse(head, tail);
            head = reverse[0];
            tail = reverse[1];
            // 把子链表重新接回原链表
            pre.next = head;
            tail.next = nex;
            pre = tail;
            head = tail.next;
        }

        return hair.next;
    }

    public ListNode[] myReverse(ListNode head, ListNode tail) {
        ListNode prev = tail.next;
        ListNode p = head;
        while (prev != tail) {
            ListNode nex = p.next;
            p.next = prev;
            prev = p;
            p = nex;
        }
        return new ListNode[]{tail, head};
    }
}

双指针

相关题目：双指针秒杀七道链表题目

21. 合并两个有序链表

21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路：比较两个链表的大小，将更小的接到p指针。

复杂度分析

• 时间复杂度：O(n+m)，其中 n和 m分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)。

• 空间复杂度：O(1)。我们只需要常数的空间存放若干变量。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while(list1!=null && list2!=null){
            if(list1.val<list2.val){
                p.next = list1;
                list1 = list1.next;
            }else{
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }
        if(list1!=null){
            p.next = list1;
        }
        if(list2!=null){
            p.next = list2;
        }
        return dummy.next;
    }
}

141. 环形链表

141. 环形链表
判断链表是否有环

思路：通过快慢指针，如果相遇则有环。
复杂度分析

• 时间复杂度：O(N)，其中N是链表中的节点数。
  当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。
  当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 NNN 轮。

• 空间复杂度：O(1)。我们只使用了两个指针的额外空间。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast=fast.next.next;
            // 快慢指针相遇则有环
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
}

nSum

拓展：一个方法团灭nSum问题

1.两数之和

1.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

思路：用map维护数组值和下标的映射关系，遍历数组的过程中如果map包含target-nums[i]则返回对应下标，没有则将当前遍历的值put到map中。
复杂度：

• 时间复杂度 O(n)
• 空间复杂度 O(n)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 维护值和下标的映射
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            int need = target-nums[i];
            if(map.containsKey(need)){
                return new int[]{map.get(need),i};
            }
            map.put(nums[i],i);
        }
        return new int[]{-1,-1};
    }
}

15. 三数之和

解题思路：排序+双指针，并且在遍历的过程中去重
时间复杂度：O(N^2)
空间复杂度：O(log⁡N)。我们忽略存储答案的空间，额外的排序的空间复杂度为 O(log⁡N)。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        
        for(int i=0;i<n;i++){
            int left = i+1;
            int right = n-1;
            while(left<right){
                int leftValue = nums[left];
                int rightValue = nums[right];
                int sum = nums[i]+leftValue+rightValue;
                if(sum==0){
                    // 找到可行解
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);
                    while(left<right && nums[right]==rightValue){
                        right--;
                    }
                	while(left<right && nums[left]==leftValue){
                        left++;
                    }
                }else if(sum>0){
                    while(left<right && nums[right]==rightValue){
                        right--;
                    }
                }else if(sum<0){
                    while(left<right && nums[left]==leftValue){
                        left++;
                    }
                }

            }
             while(i+1<n && nums[i]==nums[i+1]){
                    i++;
            }
        }
        return res;
    }
}