Hot100方法及易错点总结2

五、

234.回文链表

/*** 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) {if(head==null)return false;if(head.next==null)return true;int count=0;ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;//slow就是中间开始的第一个元素，不论是奇数还是偶数，他都是第一个元素}ListNode p=head;while(p.next!=slow){p=p.next;}//循环结束后p.next=middle;p.next=null;//前后断开才行//后半部分用尾插法ListNode reverse=new ListNode(0);ListNode q=slow;while(slow!=null){q=slow;slow=slow.next;q.next=reverse.next;reverse.next=q;}//逆序后，第二个链表的元素是reverse.nextListNode head2=reverse.next;while(head!=null&&head2!=null){if(head.val!=head2.val){return false;}head=head.next;head2=head2.next;}return true;}
}

1.易错点：前半部分和后半部分需要断开
2.还是翻转链表的问题
3.
while(slow!=null){q=slow;slow=slow.next;q.next=reverse.next;reverse.next=q;}
//循环变量是slow,不能写成q啊，这个笔误真讨厌
4. while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;//slow就是中间开始的第一个元素，不论是奇数还是偶数，他都是第一个元素}

141.环形链表

这次竟然没费什么周折直接做出来了，果然第二遍做题就是不一样

1.A和B一起跑步，A比B快，如果A能和B相遇，那一定是A比B多跑了n圈

/*** 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) {//当fast和slow第一次相等的时候，fast比slow多跑了一圈，ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(fast==slow){return true;}}return false;}
}

六、

142. 环形链表II

思路：
1.设快指针走的步数是f,慢指针走的步数是s,f=2s
当快慢指针第一次相遇的时候，(f-a)=(s-a)+nb ,快指针在环上套圈了b
综合求得到s=nb
2.到达环入口的节点(示例中图1)走的长度为a+nb, 第一次相遇时b走了nb,所以b再走a步就到入口，同时另一个指针每次走一步，走a步也到入口。

/*** 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) {ListNode fast=head;ListNode slow=head;int flag=0;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(fast==slow){//此刻slow走了nbfast=head;while(fast!=slow){fast=fast.next;slow=slow.next;}return slow;}}return null;   }
}

21.合并两个有序链表

一道常规题，p和q写的时候要注意，不能把p写成q,这样会陷入死循环，眼花找不出错误。

/*** 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) {ListNode p=list1;ListNode q=list2;ListNode L=new ListNode(0);ListNode l=L;while(p!=null&&q!=null){if(p.val<q.val){l.next=p;l=l.next;p=p.next;}else{l.next=q;l=l.next;q=q.next;}}while(p!=null){l.next=p;l=l.next;p=p.next;}while(q!=null){l.next=q;l=l.next;q=q.next;   }return L.next;}
}

2.两数相加

1.不能先将两数用int保存下来，然后再计算，这样不仅效率不高，而且如果数字过大，超过了int的取值范围，会有数值溢出的风险
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 ListNode addTwoNumbers(ListNode l1, ListNode l2) {int carry=0;ListNode L=new ListNode(0);//尾插法的头节点ListNode l=L;while(l1!=null&&l2!=null){ListNode p=l1;ListNode q=l2;l1=l1.next;l2=l2.next;int tmp=(p.val+q.val+carry)%10;carry=(p.val+q.val+carry)/10;ListNode tmpnode=new ListNode(tmp);l.next=tmpnode;l=l.next;}while(l1!=null){ListNode p=l1;l1=l1.next;int tmp=(p.val+carry)%10;carry=(p.val+carry)/10;ListNode tmpnode=new ListNode(tmp);l.next=tmpnode;l=l.next;}while(l1!=null){ListNode p=l1;l1=l1.next;int tmp=(p.val+carry)%10;carry=(p.val+carry)/10;ListNode tmpnode=new ListNode(tmp);l.next=tmpnode;l=l.next;}while(l2!=null){ListNode q=l2;l2=l2.next;int tmp=(q.val+carry)%10;carry=(q.val+carry)/10;ListNode tmpnode=new ListNode(tmp);l.next=tmpnode;l=l.next;}if(carry>0){ListNode tmpnode=new ListNode(carry);l.next=tmpnode;l=l.next;}return L.next;}
}

尾插法：
1.首先要保证便利l1,l2时，保存了第一个节点的信息之后要和后面的节点断开，不然会形成连锁反应
2.用l遍历新建立的链表，l，每次指向链表的末尾，L永远指向头节点

19.删除链表的倒数第n个节点

删除链表的节点的时候，第一个节点的删除和其他节点不一样，为了保证大家都一样，需要添加一个虚拟头节点，这样操作起来就一样了。

/*** 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 l=head;int count=0;//总的元素的个数while(l!=null){count++;l=l.next;}ListNode dummy=new ListNode(0);dummy.next=head;count++;//加上虚拟头节点，链表中节点的个数是count个。//原链表中倒数第n个节点，在原链表中排序是count+1-n;新链表中的排序是count-n;//原链表中倒数第n个节点的前一个节点，在新链表中是count-n-1l=dummy;int number=0;while(number<count-n-1){l=l.next;number++;}l.next=l.next.next;return dummy.next;}
}

七、

24.两两交换链表中的节点

1.每次需要将新链表末尾元素.next指向l2的第一个元素，这样才能把链表串起来.
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 ListNode swapPairs(ListNode head) {if(head==null||head.next==null)return head;ListNode dummy=new ListNode(0);ListNode d=dummy;ListNode p=head;//用p来遍历链表ListNode q=head.next;while(p!=null&&p.next!=null ){q=p.next;d.next=q;p.next=q.next;q.next=p;d=p;p=p.next;}return dummy.next;}
}

25.K个一组翻转链表(坑点很多，必须多做几遍)

/*** 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 reverseKGroup(ListNode head, int k) {// 边界情况处理if (head == null || head.next == null) return head;// 哑节点用于简化操作ListNode dummy = new ListNode(0);ListNode pre=dummy;dummy.next = head;while(head!=null){ListNode first_end=findEnd(head,k);if(first_end==null)break;ListNode seconde_head=first_end.next;ListNode first_rev_head=reverseNode(head,first_end);//与前面连接pre.next= first_rev_head;//！！！！与后面连接，不然没办法遍历了head.next=seconde_head;//更新pre 和head进入下一个区间pre=head;//head是当前节点的尾巴head=seconde_head;}return dummy.next;}// 找到 k 组的结尾节点（第 k 个节点），如果不足 k 个返回 nullpublic ListNode findEnd(ListNode head, int k) {ListNode dummy=new ListNode(0);dummy.next=head;ListNode p = dummy;int count=0;while(p!=null&&count<k){p=p.next;count++;}return p; // 返回第 k 个节点}// 反转从 head 到 end 之间的链表，并返回新的头部public ListNode reverseNode(ListNode head, ListNode end) {ListNode dummy=new ListNode(0);dummy.next=head;ListNode p=head;ListNode nextHead=end.next;//必须用nextHead来标记，end在移动的过程中会变的while(p!=nextHead){ListNode p_next=p.next;p.next=dummy.next;dummy.next=p;p= p_next;}return dummy.next;}}

138.随机链表的复制

/*
// 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) {Node p=head;//使用p来遍历原来链表的head;while(p!=null){Node q=new Node(p.val);Node p_next=p.next;p.next=q;q.next= p_next;p=p_next;}//每个节点复制了一个，插入了原结点的后面//复制randomwhile (p != null) {if (p.random != null) {p.next.random = p.random.next;}p = p.next.next;}// 第三步：拆分链表，恢复原链表并构造复制链表p = head;Node newHead = head.next;Node q = newHead;while (p != null) {p.next = p.next.next;if (q.next != null) {q.next = q.next.next;q = q.next;}p = p.next;}return newHead;}
}

148.排序链表

/*** 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 sortList(ListNode head) {if (head == null || head.next == null) return head;// 找到链表的结尾ListNode tail = head;while (tail.next != null) {tail = tail.next;}// 归并排序return Mergesort(head, tail);}// 找链表的中间前驱节点（返回 slow 前一个节点）public ListNode findMiddlePre(ListNode head) {if (head == null || head.next == null) return null;ListNode slow = head, fast = head, prev = null;while (fast != null && fast.next != null) {prev = slow;slow = slow.next;fast = fast.next.next;}return prev; // 返回 slow 之前的节点}public ListNode Mergesort(ListNode head, ListNode tail) {if (head == tail) {return head;}ListNode middlePre = findMiddlePre(head);ListNode middle = middlePre.next;middlePre.next = null; // 断开链表// 递归排序ListNode left = Mergesort(head, middlePre);ListNode right = Mergesort(middle, tail);// 归并return merge(left, right);}// 归并两个有序链表public ListNode merge(ListNode left, ListNode right) {ListNode dummy = new ListNode(0);ListNode p = dummy;while (left != null && right != null) {if (left.val < right.val) {p.next = left;left = left.next;} else {p.next = right;right = right.next;}p = p.next;}// 连接剩余部分if (left != null) p.next = left;if (right != null) p.next = right;return dummy.next;}
}

1.易错点：在合并的时候才创建虚拟头节点进行合并，不能在递归传入，因为会改变值ListNode left=Mergesort(head,middle_pre,p);
2.链表合并的时候需要连接剩余部分，这点一定不能忘记

New

23.合并k个升序链表（看懂未做）

146.LRU缓存（未做）

二叉树的中序遍历

1.递归方法最好写成void类型，不容易出错
2.首先拿一个点的树判断逻辑，再拿三个节点的树来判断逻辑

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

104.二叉树的最大深度

按照上面的思路来的，1.空节点2.一个节点2.三个节点

class Solution {public int maxDepth(TreeNode root) {if(root==null)return 0;int left =maxDepth(root.left)+1;int right =maxDepth(root.right)+1;return Math.max(left,right);}}

226.翻转二叉树

关于树的题越做越有感觉了，竟然又一次过了，哈哈哈哈哈
1.先考虑空节点的情况，空则怎么办
2.如果是一个节点呢，三个节点呢，处理完简单三个节点呢

/*** 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 TreeNode invertTree(TreeNode root) {invertT(root);return root;}public void invertT(TreeNode root) {if(root==null) return ;TreeNode temp=root.left;root.left=root.right;root.right=temp;invertTree(root.left);invertTree(root.right);}
}

101.对称二叉树

1.先找到最小的子问题 也就是树只有两个节点
2.找到所有能直接返回的条件，否则才会递归

/*** 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 boolean isSymmetric(TreeNode root) {if(root==null)return false;return isTwoSymmetric(root.left,root.right);}public boolean isTwoSymmetric(TreeNode One,TreeNode Two) {if(One==null&&Two==null)return true;if(One==null||Two==null)return false;//One和Two均非空if(One.val!=Two.val)return false;return (isTwoSymmetric(One.left,Two.right)&&isTwoSymmetric(One.right,Two.left));}}   

543. 二叉树的直径

易错点：
1.直径是左节点高度+右节点高度
2.高度是Math.max(left,right)+1;
3.height(TreeNode root,int max)
这样的max是局部变量，不是全局变量！！！！！

/*** 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 {private int max;public int diameterOfBinaryTree(TreeNode root) {height(root);return max;}public int height(TreeNode root){if(root==null)return 0;int left =height(root.left);int right =height(root.right);int len=Math.max(left,right)+1;max=Math.max(max,left+right);return len;    }
}

102.二叉树的层序遍历（看懂未做）

108.将有序数组转换为二叉搜索树(看懂未做)

98.验证二叉搜索树（看懂未做）

230.二叉搜索树中第k小的元素（有思路未做）

二叉搜索树中序遍历会得到有序数组，这是一个很重要的特性

199.二叉树的右视图（看懂未做）

114.二叉树展开为链表（看懂未做）

105.从前序与中序遍历序列构造二叉树（看懂未做）