链表+二叉树
·
一、链表
1. 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
「链表 headA」的节点数量为 a ，「链表 headB」的节点数量为 b ，「两链表的公共尾部」的节点数量为 c
指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：
a+(b−c)
指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：
b+(a−c)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A = headA;
ListNode B = headB;
while(A!=B){ //只要A/B不为空就往下走，走到尾则跳到另一个头
A = A!= null ? A.next : headB;
B = B!= null ? B.next : headA;
}
//第一次相遇就在公共节点
return A;
}
}2. 反转链表
主要是三个指针的移动，先移动cur.next,再移动pre,最后再移动cur。细节：在while里面先创建一个next，为了最后的cur移动。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
//方法一：迭代
class Solution {
//官方题解：迭代
public ListNode reverseList(ListNode head) {
ListNode pre = null; //新的头结点的引用
ListNode cur = head;
while(cur!=null){
ListNode next = cur.next;
//重点是这三个指针的移动
cur.next = pre;
//必须要先移动pre，再移动cur，否则会丢失前节点
pre = cur;
cur = next;
}
return pre;
}
}
//方法二：递归3. 回文链表-@官方题解一
其实很简单。总共就两步：1、把链表每个节点的值复制到数组当中，数组.add(cur.val)。2、双指针分别从最前面和最后面对比是否相同。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<Integer>(); //创建数组
//将链表值赋值到数组中
ListNode cur = head;
while(cur!=null){
vals.add(cur.val);
cur = cur.next;
}
//双指针判断回文
int front = 0;
int back = vals.size()-1;
while(front < back){
if(!vals.get(front).equals(vals.get(back))){
return false;
}
front ++;
back --;
}
return true;
}
}4. 环形链表（判断链表有无环）-官方题解方法二
思路也很简单。首先特判：要是头结点为空，或头结点.next为空，也就是只有一个节点，都不可能成环。总体思路：快慢指针，慢移动一个，快移动两个，如果 fast==null 或 fast.next == null,说明无环 return false，若快慢相遇说明有环。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
//官方题解方法二
public class Solution {
public boolean hasCycle(ListNode head) {
//特判
if(head == null || head.next == null){
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while(slow != fast){
if(fast == null || fast.next == null){
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}5. 环形链表Ⅱ-官方题解：方法二
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
其实也是定义快慢指针，只是在上一题基础上，当快慢相遇的时候，重新定义一个指针从头结点跟慢指针一起移动，相遇的节点就是环入口。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null ){
return null;
}
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
ListNode ptr = head;
while(ptr != slow){
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}
}6. 合并两个有序链表-@腐烂的橘子-递归
主要理解递归思想，逐个比较链表数值，小的那个list.next = 新的list继续merge
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1==null){
return list2;
}else if(list2==null){
return list1;
}else if(list1.val<list2.val){
list1.next = mergeTwoLists(list1.next,list2);
return list1;
}else{
list2.next = mergeTwoLists(list2.next,list1);
return list2;
}
}
}7. 两数相加-@画手大鹏
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
技巧：当题目需要返回头结点的时候，可以创建一个虚拟结点指向头结点。下一题也是
8. 删除链表的倒数第N个结点-@画手大鹏
思路：1、fast先向前移动n个节点。2、slow和fast同步移动直到fast在最后一个。3、删除slow的下一个节点。
- 删除后返回
pre.next，为什么不直接返回head呢，因为head有可能是被删掉的点/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode pre = new ListNode(0); pre.next = head; ListNode fast = pre, slow = pre; while(n>0){ //完成while后此时slow和fast相差n fast = fast.next; n--; } //fast和slow一起同步移动直到fast是最后一个 while(fast.next != null){ fast = fast.next; slow = slow.next; } //此时slow的下一个节点就是要删除的节点 slow.next = slow.next.next; return pre.next; } }9. 两两交换链表中的节点-@画手大鹏
-
递归思想，创建节点newHead = head.next，然后先移动head.next = swapPairs（newHead）。再移动newHead.next = head。顺序不能错，因为第一步要依赖newHead.next.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode swapPairs(ListNode head) { if(head == null || head.next == null){ return head; } ListNode newHead = head.next; head.next = swapPairs(newHead.next); newHead.next = head; return newHead; } }10. 随机链表的复制-@Krahets方法一：哈希表
-
这里的random没用的，就是看成多了一个指针而已。
-
哈希表key是原节点，value是对应的复制节点。
-
第一次遍历复制cur.val，第二次遍历定义next指针和random指针。
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
//特判
if(head == null) return null;
Node cur = head;
//key是原节点，value是复制节点
Map<Node,Node> map = new HashMap<>();
//两次遍历，第一次构造节点值，第二次构造指针指向
while(cur!=null){
map.put(cur,new Node(cur.val));
cur = cur.next;
}
cur = head;//第一次遍历完之后重新指向头结点
while(cur != null){
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
//返回新链表的头结点
return map.get(head);
}
}11. LRU缓存-@官方题解
二、二叉树
1. 二叉树的中序遍历-@官方题解：递归
重点是那个中序遍历函数，写清楚调用的顺序。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
//官方题解，递归
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorder(root,res);
return res;
}
public void inorder(TreeNode root,List<Integer> res){
if(root == null){
return;
}
inorder(root.left,res);
res.add(root.val);
inorder(root.right,res);
}
}2. 二叉树的最大深度-@官方题解法一：DFS递归
如果我们知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为
max(l,r)+1。同样也是递归，对比递归终止条件
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}else{
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight,rightHeight)+1;
}
}
}3. 翻转二叉树-@官方题解-递归
对比递归终止条件。
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/invert-binary-tree/solutions/415160/fan-zhuan-er-cha-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。4. 对称二叉树-@Krahets-DFS递归
重点是recur函数：
1、递归终止的true（左右子树均null）和false条件（左右其中一个为空 || 左右节点值不相同）
2、再判断recur（左的左，右的右）|| （左的右，右的左）
class Solution {
public boolean isSymmetric(TreeNode root) {
return root == null || recur(root.left, root.right);
}
boolean recur(TreeNode L, TreeNode R) {
if (L == null && R == null) return true;
if (L == null || R == null || L.val != R.val) return false;
return recur(L.left, R.right) && recur(L.right, R.left);
}
}
作者：Krahets
链接：https://leetcode.cn/problems/symmetric-tree/solutions/2361627/101-dui-cheng-er-cha-shu-fen-zhi-qing-xi-8oba/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。5. 二叉树的直径-官方题解评论区-@捷少
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
class Solution {
int maxd=0;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return maxd;
}
public int depth(TreeNode node){
if(node==null){
return 0;
}
int Left = depth(node.left);
int Right = depth(node.right);
//将每个节点最大直径(左子树深度+右子树深度)当前最大值比较并取大者
maxd=Math.max(Left+Right,maxd);
return Math.max(Left,Right)+1;//返回节点深度
}
}
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
6
0- 0
已为社区贡献1条内容
所有评论(0)