第一页总结

第一页总结

• 链表
• • 反转
  • • 206. 反转链表
    • 25. K 个一组翻转链表
  • 双指针
  • • 21. 合并两个有序链表
    • 141. 环形链表
• 二叉树
• • 102. 二叉树的层序遍历
  • 236. 二叉树的最近公共祖先
• 数组
• • 1.两数之和
  • 15. 三数之和

链表

反转

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

二叉树

102. 二叉树的层序遍历

102. 二叉树的层序遍历
思路：通过队列来实现二叉树的层序遍历，通过while循环判断队列是否为空控制二叉树从上到下的遍历，根据当前队列的size用for循环控制每一层从左到右的遍历。

时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)。
空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new LinkedList<>();
        if(root==null){
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // while循环控制从上向下遍历
        while(!queue.isEmpty()){
            int size = queue.size();
            // for循环控制该层从左到右遍历
            List<Integer> curRes = new ArrayList<>();
            for(int i=0;i<size;i++){
                TreeNode node = queue.poll();
                curRes.add(node.val);
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }   
            }
            result.add(curRes);

        }
        return result;
    }
}

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。p和q一定存在于二叉树中。
最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路：找p和q的公共祖先，就是找以root为根的二叉树中寻找p或q的节点。如果root为p或q直接返回root，接着递归的遍历左右子树，如果在左右子树分别找到了p和q则返回root，如果p和q都没在以root为根的节点找到则返回null，如果p和q存在一个则返回那个节点。
复杂度分析：

• 时间复杂度：O(N)，其中 N是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为 O(N)。
• 空间复杂度：O(N) ，其中 N是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)。

class Solution {
    //定义：在以 root 为根的二叉树中寻找值为 p 或 q 的节点
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        // base case: 找到p或q
        if(root.val==p.val || root.val==q.val){
            return root;
        }
        // 从root的左右子树找
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 情况一：分别在左右子树找到了p和q
        if(left!=null && right!=null){
            return root;
        }
        return left==null?right:left;
    }
}

数组

拓展：一个方法团灭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;
}
}