一 两链表相交
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) {
Set<Node> nodeSet = new HashSet<>();
//此字段仅用来记录遍历次数
int traverseCount = 0;
while (node != null) {
if (nodeSet.contains(node)) {
Log.d(TAG, "hasCycle2==>有环...traverseCount="+traverseCount);
return true;
}
traverseCount ++;
Log.d(TAG, "hasCycle2==>traverseCount="+traverseCount);
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;
}
}
// 找到链表第一个入环节点，如果无环，返回null
public static Node getLoopNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
// n1 慢 n2 快
Node slow = head.next; // n1 -> slow
Node fast = head.next.next; // n2 -> fast
while (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 head
while (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
分析
先都让两个无环的链表走到最后，看是最后一个节点的内存地址是否相等，不相等一定不相交，end1==end2那么他们是一定相交的，end1和end2是他们相交的最后一个节点，要求的是第一个相交的节点，让长的一个走先他多出来的节点，再让短的和他们一起走，当有相等的时候那么这个点就是他们相交的第一个节点；
代码
// 如果两个链表都无环，返回第一个相交节点，如果不想交，返回null
public 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; // 谁长，谁的头变成cur1
cur2 = cur1 == head1 ? head2 : head1; // 谁短，谁的头变成cur2
n = 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 代码
// 两个有环链表，返回第一个相交节点，如果不想交返回null
public 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;
}
// 1
f(head.left);
// 2
f(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) {
Stack<Node> stack = new Stack<Node>();
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) {
Stack<Node> stack = new Stack<Node>();
//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) {
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
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();
}
