o2o手机网站建设难,给公司做个网页要多少钱,北京建设网站设计,改wordpress评论邮箱一 两链表相交
1.1 题目描述 给定两个可能有环也可能无环的单链表#xff0c;头节点head1和head2。请实现一个函数#xff0c;如果两个链表相交#xff0c;请返回相交的 第一个节点。如果不相交#xff0c;返回null 【要求】 如果两个链表长度之和为N#xff0c;时间复杂…
一 两链表相交
1.1 题目描述 给定两个可能有环也可能无环的单链表头节点head1和head2。请实现一个函数如果两个链表相交请返回相交的 第一个节点。如果不相交返回null 【要求】 如果两个链表长度之和为N时间复杂度请达到O(N)额外空间复杂度 请达到O(1)。 1.2 判断一个单链表是否有环
情况 假如一个单链表给你一个头节点如果有环的话返回第一个入环的节点如果无环的话返回null
1.2.1 方案一 容器的办法 Set集合
1.2.1.1 假如链表无环走到null的时候在hashset里面都没有找到重复的 假如链表是有环的遍历链表的判断当前链表每个节点判断当前节点是否在hashset里面如果在就说明有环如果不在将该节点放入set里面如果遍历到最后一个null后m都没找到有在hash里面的节点说明无环
1.2.1.2 代码
//快慢指针public boolean hasCycle(ListNode head) {if (head 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;}
}
/*** 通过Set集合记录值的方式如果有重复的数据就代表有环* param node* return*/private boolean hasCycle2(Node node) {SetNode nodeSet new HashSet();//此字段仅用来记录遍历次数int traverseCount 0;while (node ! null) {if (nodeSet.contains(node)) {Log.d(TAG, hasCycle2有环...traverseCounttraverseCount);return true;}traverseCount ;Log.d(TAG, hasCycle2traverseCounttraverseCount);nodeSet.add(node);node node.next;}Log.d(TAG, hasCycle2无环);return false;}
1.2.1.3 总结
链表的环可能有很多但单链表只有一个next指针不会出现分叉的情况
1.2.2 使用快慢指针遍历链表
思路使用快慢指针遍历链表快指针一旦走到
null则该单链表一定无环快指针一次走两步如果存在环的话快指针与慢指针一定会在环上相遇。
当快慢指针相遇时让快指针重新指向初始节点慢指针原地不变两个指针都每次走一步一定会在链表的入环节点相遇
1.2.2.1 分析
情况一 如果快指针走到null了说明无环
如下情况图解找到相遇的点但不是相交的入口节点再做图二的解析当相遇的时候快指针去到链表的头慢指针留在原地继续走这个时候快慢指针都只走一步这样再次往前走的话他两一定会在入口节点相遇这个相遇的点就为入口的交点 1.2.2.2 代码
public static class Node {public int value; public Node next; public Node(int data) {this.value data; }
}
// 找到链表第一个入环节点如果无环返回nullpublic static Node getLoopNode(Node head) {if (head null || head.next null || head.next.next null) {return null;}// n1 慢 n2 快Node slow head.next; // n1 - slowNode fast head.next.next; // n2 - fastwhile (slow ! fast) {if (fast.next null || fast.next.next null) {return null;}fast fast.next.next;slow slow.next;}// slow fast 相遇fast head; // n2 - walk again from headwhile (slow ! fast) {slow slow.next;fast fast.next;}return slow;}
1.2.2.3 总结 快慢指针找链表入环的节点 1、找到相遇点 2、快指针去到链表头再都分别往前走就能找到 1.3 本题分析 情况一 两个链表都无环的情况-存在相交 情况二 如果两个链表一个无环一个有环-不存在相交因为相交后只存在一个next只有一个有环需要两个next 情况三 两个都有环 的情况这个环在相交节点后成一个环 情况一 情况二 情况三两个链表有环的情况 1.3.1 情况一 两个链表都无环的情况-存在相交
1.3.1.1 hashset
先判断两个链表都没环的情况先通过上面的方法判断每个链表是否有环再利用hashset先将一个链表放入hashset里面再遍历宁一个链表是否有节点在haseset里面 1.3.1.2 二不使用hashset
分析
先都让两个无环的链表走到最后看是最后一个节点的内存地址是否相等不相等一定不相交end1end2那么他们是一定相交的end1和end2是他们相交的最后一个节点要求的是第一个相交的节点让长的一个走先他多出来的节点再让短的和他们一起走当有相等的时候那么这个点就是他们相交的第一个节点
代码
// 如果两个链表都无环返回第一个相交节点如果不想交返回nullpublic static Node noLoop(Node head1, Node head2) {if (head1 null || head2 null) {return null;}Node cur1 head1;Node cur2 head2;int n 0;while (cur1.next ! null) {n;cur1 cur1.next;}while (cur2.next ! null) {n--;cur2 cur2.next;}//判断是否相交if (cur1 ! cur2) {return null;}// n : 链表1长度减去链表2长度的值cur1 n 0 ? head1 : head2; // 谁长谁的头变成cur1cur2 cur1 head1 ? head2 : head1; // 谁短谁的头变成cur2n Math.abs(n);while (n ! 0) {n--;cur1 cur1.next;}while (cur1 ! cur2) {cur1 cur1.next;cur2 cur2.next;}return cur1;}
1.3.2 情况二
分析 如果两个链表一个无环一个有环-不存在相交因为相交后只存在一个next要一个有环需要两个next
1.3.3 情况三 情况三 两个都有环 的情况这个环在相交节点后成一个环 当loop1 和loop2相等的化就是情况三的第二种 当loop1 和loop2不相等的化就是情况三的第一种和第三种 1.3.3.1 loop1 loop2 当loop1 和loop2相等的化、话就是情况三的第二种,求第一个交点 分析 当loop1 和loop2终止点时就和情况一中的求无环链表的第一个交点一样 1.3.3.2 loop1 ! loop2 当loop1 和loop2不相等的化就是情况三的第一种和第二种 分析 loop1环节点开始我转一圈的过程中如果越到loop2说明是情况三 loop1 和 loop2都是他两的相交节点 没有越到说明是情况1没有相交节点情况1返回null 1.3.3 代码
// 两个有环链表返回第一个相交节点如果不想交返回nullpublic static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {Node cur1 null;Node cur2 null;if (loop1 loop2) {cur1 head1;cur2 head2;int n 0;while (cur1 ! loop1) {n;cur1 cur1.next;}while (cur2 ! loop2) {n--;cur2 cur2.next;}cur1 n 0 ? head1 : head2;cur2 cur1 head1 ? head2 : head1;n Math.abs(n);while (n ! 0) {n--;cur1 cur1.next;}while (cur1 ! cur2) {cur1 cur1.next;cur2 cur2.next;}return cur1;} else {cur1 loop1.next;while (cur1 ! loop1) {if (cur1 loop2) {return loop1;}cur1 cur1.next;}return null;}}1.3.4 主函数调用
public static Node getIntersectNode(Node head1, Node head2) {if (head1 null || head2 null) {return null; }Node loop1 getLoopNode(head1); Node loop2 getLoopNode(head2); if (loop1 null loop2 null) {return noLoop(head1, head2); }if (loop1 ! null loop2 ! null) {return bothLoop(head1, loop1, head2, loop2); }return null;}二 二叉树的先序、中序、后序遍历
2.1 递归实现
2.1.1 前中后遍历的讲解 先序 中序 后序 都可以由以下函数改出来把打印放在第一次第二次第三次就是对应的前中后遍历
递归序
充分理解递归点过程根据递归的实现原理
2.1.2 代码
package class10;public class Code02_RecursiveTraversalBT {public static class Node {public int value;public Node left;public Node right;public Node(int v) {value v;}}public static void f(Node head) {if (head null) {return;}// 1f(head.left);// 2f(head.right);// 3}// 先序打印所有节点public static void pre(Node head) {if (head null) {return;}System.out.println(head.value);pre(head.left);pre(head.right);}public static void in(Node head) {if (head null) {return;}in(head.left);System.out.println(head.value);in(head.right);}public static void pos(Node head) {if (head null) {return;}pos(head.left);pos(head.right);System.out.println(head.value);}public static void main(String[] args) {Node head new Node(1);head.left new Node(2);head.right new Node(3);head.left.left new Node(4);head.left.right new Node(5);head.right.left new Node(6);head.right.right new Node(7);pre(head);System.out.println();in(head);System.out.println();pos(head);System.out.println();}}
2.2 非递归实现-
2.2.1 前序遍历
2.2.1.1 分析
2.2.1.2 代码
public static class Node {public int value;public Node left;public Node right;public Node(int v) {value v;}}public static void pre(Node head) {System.out.print(pre-order: );if (head ! null) {StackNode stack new StackNode();stack.add(head);while (!stack.isEmpty()) {head stack.pop();System.out.print(head.value );if (head.right ! null) {stack.push(head.right);}if (head.left ! null) {stack.push(head.left);}}}System.out.println();}
2.2.2 中序遍历 2.2.2.1 分析 2.2.2.2 代码
public static void in(Node cur) {System.out.print(in-order: );if (cur ! null) {StackNode stack new StackNode();//cur null 还需要继续保证往下通过!stack.isEmpty()while (!stack.isEmpty() || cur ! null) {if (cur ! null) {stack.push(cur);cur cur.left;//1、假如上面的最后一个节点 cur d.left;} else {//2、cur null 弹出 cur stack.pop(); 为d//3、找cur cur.right;还是空还是来到这个循环//4、弹出的就是b了cur stack.pop();为e了继续往下走//5、e的左右都为空再弹出的就是a了cur stack.pop();System.out.print(cur.value );cur cur.right;}}}System.out.println();}
2.2.3 后续遍历
2.2.3.1 在先序遍历的基础上进行修改 先改出一个头右左去压栈压栈的时候先左再右弹出来就对了从新栈出来就是左右头就是后续遍历
先在压栈头左右基础上改出一个压栈为头右左的形式弹出的时候不立马打印而是先压入一个栈里面最后再弹出就是后续遍历
左右头
2.2.3.2 代码
public static void pos1(Node head) {System.out.print(pos-order: );if (head ! null) {StackNode s1 new StackNode();StackNode s2 new StackNode();s1.push(head);while (!s1.isEmpty()) {head s1.pop(); // 头 右 左s2.push(head);if (head.left ! null) {s1.push(head.left);}if (head.right ! null) {s1.push(head.right);}}// 左 右 头while (!s2.isEmpty()) {System.out.print(s2.pop().value );}}System.out.println();}扩展见代码 用一个栈来实现
三 附加题 X 祖先节点 交集 后边再看
