206 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]分析：
在遍历链表时，将当前节点的 \textit{next}next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
实现：
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) {
return head;
}
ListNode pre = null;
while(head != null) {
ListNode next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}3 无重复字符的最长子串
给定一个字符串?s?，请你找出其中不含有重复字符的?最长子串?的长度。
示例：
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。分析：
?实现：
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null) {
return 0;
}
int length = s.length();
int right = 0;
int result = 0;
Set<Character> set = new HashSet();
for(int i = 0; i < length ; i ++) {
if(i != 0) {
set.remove(s.charAt(i - 1));
}
while(right < length && !set.contains(s.charAt(right))) {
set.add(s.charAt(right));
right ++;
}
result = Math.max(result, right - i);
}
return result;
}
}?53 最大子数组和
给你一个整数数组?nums?，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组?是数组中的一个连续部分。
示例：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。解题：
代码：
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0;
int result = nums[0];
for(int x : nums) {
pre = Math.max(pre + x, x);
result = Math.max(pre, result);
}
return result;
}
}?21 合并两个有序链表
将两个升序链表合并为一个新的?升序?链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。?
示例：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]思路：
?代码：?
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode temp = new ListNode(-1);
ListNode current = temp;
while(list1 != null && list2 != null) {
if(list1.val > list2.val) {
current.next = list2;
list2 = list2.next;
} else {
current.next = list1;
list1 = list1.next;
}
current = current.next;
}
if(list1 != null) {
current.next = list1;
}
if(list2 != null) {
current.next = list2;
}
return temp.next;
}
}1 两数之和
给定一个整数数组 nums?和一个整数目标值 target，请你在该数组中找出 和为目标值 target??的那?两个?整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
方法二实现?
代码：
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap();
for(int i = 0; i < nums.length; i ++) {
if(map.containsKey(target - nums[i])) {
result[0] = i;
result[1] = map.get(target - nums[i]);
return result;
}
map.put(nums[i], i);
}
return result;
}
}?102 二叉树的层序遍历
给你二叉树的根节点?root?，返回其节点值的?层序遍历?。 （即逐层地，从左到右访问所有节点）。
示例：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
?代码：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList();
if(root == null) {
return list;
}
Deque<TreeNode> deque = new ArrayDeque();
deque.offer(root);
while(!deque.isEmpty()) {
int size = deque.size();
List<Integer> levelList = new ArrayList();
for(int i = 0; i < size; i ++) {
TreeNode node = deque.poll();
levelList.add(node.val);
if(node.left != null) {
deque.offer(node.left);
}
if(node.right != null) {
deque.offer(node.right);
}
}
list.add(levelList);
}
return list;
}
}141 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递?。仅仅是为了标识链表的实际情况。
如果链表中存在环?，则返回 true 。 否则，返回 false 。
示例：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。代码：
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet();
while(head != null) {
if(set.contains(head)) {
return true;
}
set.add(head);
head = head.next;
}
return false;
}
}你两个单链表的头节点?headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> set = new HashSet();
while(headA != null) {
set.add(headA);
headA = headA.next;
}
while(headB != null) {
if(set.contains(headB)) {
return headB;
}
headB = headB.next;
}
return null;
}
}给定一个链表的头节点 ?head?，返回链表开始入环的第一个节点。?如果链表无环，则返回?null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null) {
return null;
}
Set<ListNode> setNode = new HashSet();
while(head != null) {
if(setNode.contains(head)) {
return head;
}
setNode.add(head);
head = head.next;
}
return null;
}
}定一个二叉树的根节点?root?，返回?它的?中序?遍历?。
代码：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList();
inorderTraversal(root, list);
return list;
}
public void inorderTraversal(TreeNode root, List<Integer> list) {
if(root == null) {
return;
}
inorderTraversal(root.left, list);
list.add(root.val);
inorderTraversal(root.right, list);
}
}给你一个链表，删除链表的倒数第?n?个结点，并且返回链表的头结点。
示例：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]代码：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode pre = new ListNode(-1);
pre.next = head;
ListNode fast = pre, slow = pre;
for(int i = 0; i <= n; i ++) {
if(fast == null) {
return pre.next;
}
fast = fast.next;
}
while(fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return pre.next;
}
}给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明:?叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]
返回它的最大深度?3 。
代码：
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}给你一个二叉树的根节点?root?， 检查它是否轴对称。
代码：
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) {
return true;
}
return isSymmetric(root.left, root.right);
}
public boolean isSymmetric(TreeNode left, TreeNode right) {
if(left == null && right == null) {
return true;
}
if(left == null || right == null) {
return false;
}
return left.val == right.val && isSymmetric(left.right, right.left)
&& isSymmetric(left.left, right.right);
}
}给你一个单链表的头节点?head?，请你判断该链表是否为回文链表。如果是，返回?true?；否则，返回?false?。
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null) {
return true;
}
List<Integer> list = new ArrayList();
while(head != null) {
list.add(head.val);
head = head.next;
}
int left = 0, right = list.size() - 1;
while(left <= right) {
if(list.get(left) != list.get(right)) {
return false;
}
left ++;
right --;
}
return true;
}
}
