方法一：借队列层序遍历每个结点，交换其左右子结点 public TreeNode Mirror (TreeNode pRoot) { // write code here if(pRoot==null)return null; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(pRoot); while(!queue.isEmpty()){ TreeNode node = queue.poll(); TreeNode temp = node.left; node.left = node.right; node...

方法一：借助队列层序遍历二叉树 public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { ArrayList<Integer> arr = new ArrayList<>();//写在最前面检验null if(root==null)return arr;//返回空数组，不能null（会报错） Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); arr.add(root.val); while(...

难点：random的深拷贝  此题难点在于要深拷贝，新链表中每一个结点都应该指向自己链表中的结点，而不能单纯保存旧表中结点的地址。 next指向下一个新结点很容易，但random是随机访问，拷贝时就要找到旧random指向的旧结点，对应的新结点是哪个,然后让新结点的random指向这个新结点。 新结点在创建时可能指向的random结点还没有被创建，因此这也是不能直接赋值random的原因，链表先链接好再去找random，也得找到新旧结点的对应关系才行。方法一：哈希表建立新旧结点间的映射 public RandomListNode Clone(RandomListNode pHead) { if...

方法一：遍历直接删除  因为链表有序，所以才能与相邻元素比较，直接删除！  没有开辟额外的存储空间！ public ListNode deleteDuplication(ListNode pHead) { if(pHead==null)return null; ListNode res =new ListNode(0); res.next = pHead; //用pre和cur来操作res链上的结点！ ListNode pre = res; ListNode cur = pHead.next; while(cur!=null){ if(pre.next.val == cur.val){ //必...

方法一：快慢指针相遇法 注意：  （1）fast以2倍速度绕圈和slow相遇之后回到起点 （2）回到起点后，fast与slow同频移动直至在入口处相遇 （3）必须考虑无环为空的情况  原理：a = c + (k-1)(b+c) public ListNode EntryNodeOfLoop(ListNode pHead) { if(pHead == null)return null;//（1）空链表 ListNode fast = pHead; ListNode slow = pHead; while(fast != null && fast.next!=null){ fast...

方法一：两个指针以同样速度走完相同长度路径必会相遇 public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { //if(pHead1==null||pHead2==null)return null; ListNode cur1 = pHead1; ListNode cur2 = pHead2; while(cur1!=cur2){ //相遇时循环停止 if(cur1==null){ //1走完就去走2 cur1 = pHead2; }else{ //只有非空时才能往下一个位置移动！ cur1 = cur1.n...

方法一：利用新链表按顺序合并  新链表有一个头结点，用于返回结果链表 新链表上有一个活动指针cur指向添加新结点的位置 两个原链表在添加结点到新链表后，应将头指针后移 空间复杂度为O（1）  -注意：题目中新链表的头结点需要分配初始空间，而不能直接赋值为null public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if(list1==null)return list2; if(list2==null)return list1; //此处必须给res赋值而不能写为null，分配空间后才能指向...

方法一：双链表——创建一个新链表，倒序链接，形成反转链表 public class Solution { public ListNode ReverseList(ListNode head) { //空链表 ListNode newHead = null; //遍历原链表 while(head!=null){ //头结点将移动，需要保存下一个结点 ListNode temp = head.next; //结点往前累积，形成倒序 head.next = newHead; //移动新结点指针到链表头部 newHead = head; //原链表head指针移动到下一个位置 head = temp;...

此题有两个方法，解题时必须考虑数组越界问题，使用if进行检查  方法一：快慢指针  链表长度未知的情况下，可以用一个指针找到输出的点位，再用另一个指针置于链表最后，相当于找到了链表的“长度”，此方法没有占用额外的储存空间，空间复杂度为O(1)   定义两个指针fast和slow，初始都置于头节点处 fast先向前移动k步，这时两个指针之间相隔k个单位 再将两个指针同步移动，直至fast移动至末尾，移动结束此时两个指针之间所夹住的部分就是要导出的链表，使用slow指针即可获取   注意：数组越界问题判断k是否大于链表长度：也即判断fast向前移动k步的过程中会不会提前到达链表末尾  Java核心...