链表高阶面试题及二叉树的遍历【前、中、后、层】

1 链表高阶面试题

1 找到第一个相交节点

给定两个可能有环也可能无环的单链表，头节点head1和head2.请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回null。
【要求】：
如果两个链表长度之和为N，时间复杂度要求O（N），额外空间复杂度为O（1）

1.1 思路

分情况讨论，首先实现一个函数getLoopNode（Node head）判断该链表是否有环，然后分情况讨论：

如果两个链表无环，实现一个noLoop（Node head1， Node head2）判断
如果两个链表都有环，实现一个bothLoop（Node head1， Node head2， Node loop1， Node loop2）判断
如果一个有一个没有，直接返回null【因为单链表情况下，该情况不可能有环】

1.2 Node节点结构

public static class Node{
    private int value;
    private Node next;

    public Node(int value){
        this.value = value;
    }
}
1
2
3
4
5
6
7
8

1.3 getLoopNode（Node head）实现：快慢指针

//返回链表的入环节点
public static Node getLoopNode(Node head){
    if(head == null || head.next == null || head.next.next == null){
        return null;
    }
    //快慢指针解决
    Node slow = head.next;
    Node fast = head.next.next;
    while(slow != fast){
        if(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        } else {
            return null;
        }
    }
    //fast、slow相遇，fast重回起点head，且速度降为1
    fast = head;
    while(fast != slow){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1.4 bothLoop（Node head1， Node head2， Node loop1， Node loop2）

//两个链表都有环的处理方式
public static Node bothLoop(Node head1, Node head2, Node loop1, 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);//n有可能为负数，因此取绝对值
        while (n > 0) {
            cur1 = cur1.next;
            n--;
        }
        //两链表差值已经弥补完了【同一起点】
        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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

1.5 noLoop（Node head1， Node head2）

//两个链表都无环
public static Node noLoop(Node head1, Node head2){
    Node cur1 = head1;
    Node cur2 = head2;
    int n = 0;
    while(cur1 != null){
        cur1 = cur1.next;
        n++;
    }
    while(cur2 != null){
        cur2 = cur2.next;
        n--;
    }
    cur1 = n > 0 ? head1 : head2;
    cur2 = cur1 == head1 ? head2 : head1;
    while(n > 0){
        cur1 = cur1.next;
        n--;
    }
    while(cur1 != null && cur2 != null){
        if(cur1 == cur2){
            return cur1;
        } else {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
    }
    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

1.6 主函数getFirstIntersectNode（Node head1， Node head2）

//返回两链表相交的第一节点【若不相交，返回null】
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 bothLoop(head1, head2, loop1, loop2);
    } else if (loop1 == null && loop2 == null) {
        //两个链表都无环
        return noLoop(head1, head2);
    } else {
        //一个链表有环，一个链表无环，不可能相交【单链表】 -> 直接返回null
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.7 全部代码

public class Code01_FindFirstIntersectNode {

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }


    //返回两链表相交的第一节点【若不相交，返回null】
    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 bothLoop(head1, head2, loop1, loop2);
        } else if (loop1 == null && loop2 == null) {
            //两个链表都无环
            return noLoop(head1, head2);
        } else {
            //一个链表有环，一个链表无环，不可能相交【单链表】 -> 直接返回null
            return null;
        }
    }


    //返回链表的入环节点
    public static Node getLoopNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        //快慢指针解决
        Node slow = head.next;
        Node fast = head.next.next;
        while (slow != fast) {
            if (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            } else {
                return null;
            }
        }
        //fast、slow相遇，fast重回起点head，且速度降为1
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    //两个链表都无环
    public static Node noLoop(Node head1, Node head2) {
        Node cur1 = head1;
        Node cur2 = head2;
        int n = 0;
        while (cur1 != null) {
            cur1 = cur1.next;
            n++;
        }
        while (cur2 != null) {
            cur2 = cur2.next;
            n--;
        }
        cur1 = n > 0 ? head1 : head2;
        cur2 = cur1 == head1 ? head2 : head1;
        while (n > 0) {
            cur1 = cur1.next;
            n--;
        }
        while (cur1 != null && cur2 != null) {
            if (cur1 == cur2) {
                return cur1;
            } else {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
        }
        return null;
    }

    //两个链表都有环的处理方式
    public static Node bothLoop(Node head1, Node head2, Node loop1, 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);//n有可能为负数，因此取绝对值
            while (n > 0) {
                cur1 = cur1.next;
                n--;
            }
            //两链表差值已经弥补完了【同一起点】
            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;
        }
    }

    public static void main(String[] args) {
        // 1->2->3->4->5->6->7->null
        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);

        // 0->9->8->6->7->null
        Node head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).value);

        // 1->2->3->4->5->6->7->4...
        head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);
        head1.next.next.next.next.next.next = head1.next.next.next; // 7->4

        // 0->9->8->2...
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next; // 8->2
        System.out.println(getIntersectNode(head1, head2).value);

        // 0->9->8->6->4->5->6..
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).value);

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176

2 二叉树的遍历

2.1 前序遍历

2.1.1 递归方式

//递归
class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        getValue(root);
        return list;
    }
    public void getValue(TreeNode root){
        if(root == null){
            return;
        }
        list.add(root.val);
        getValue(root.left);
        getValue(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.1.2 非递归方式

//非递归方法：根左右【先进右->栈】
class Solution {
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<Integer> stack = new Stack<>();
        fun(root);
        return list;
    }
    public void fun(TreeNode root){
        if(root == null){
            return;
        }
        stack.push(root);
        TreeNode node = null;
        while(!stack.isEmpty()){
            node = stack.pop();
            list.add(node.val);
            if(node.right != null){
                stack.add(node.right);
            }
            if(node.left != null){
                stack.add(node.left);
            }
        }
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2.2 中序遍历

2.2.1 递归方式

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        getVal(root);
        return list;
    }
    public void getVal(TreeNode root){
        if(root == null){
            return;
        }
        getVal(root.left);
        list.add(root.val);
        getVal(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.2.2 非递归【一直左】

先一次性全部进左，然后判断，再进右

//中序：左根右
class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        fun(root);
        return list;
    }
    public void fun(TreeNode root){
        if(root != null){
            Stack<TreeNode> stack = new Stack<>();
            while(!stack.isEmpty() || root != null){
                if(root != null){
                    stack.push(root);
                    root = root.left;
                } else {
                    root = stack.pop();
                    list.add(root.val);
                    root = root.right;
                }
            }
        }
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2.3 后序遍历

2.3.1 递归

//后序遍历：递归【左右根】
class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        getValue(root);
        return list;
    }
    public void getValue(TreeNode root){
        if(root == null){
            return;
        }
        getValue(root.left);
        getValue(root.right);
        list.add(root.val);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.3.2 非递归

//后序：左右根
//根右左
class Solution {
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        fun(root);
        return list;
    }
    public void fun(TreeNode root){
        if(root == null){
            return;
        }
        stack1.push(root);
        //根右左
        while(!stack1.isEmpty()){
            root = stack1.pop();
            stack2.push(root);
            //根右左
            //先压左，弹出的时候就是后弹左 -> 右 左
            if(root.left != null){
                stack1.push(root.left);
            }
            if(root.right != null){
                stack1.push(root.right);
            }
        }
        while(!stack2.isEmpty()){
            list.add(stack2.pop().val);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

2.4 层序遍历【size】

//层序遍历【size】
class Solution {
    public List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        fun(root);
        return res;
    }
    public void fun(TreeNode root){
        if(root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int size = 0;
        while(!queue.isEmpty()){
            size = queue.size();//弹几次
            List<Integer> list = new ArrayList<>();
            while(size > 0){
                root = queue.poll();
                list.add(root.val);
                if(root.left != null){
                    queue.add(root.left);
                }
                if(root.right != null){
                    queue.add(root.right);
                }
                size--;
            }
            res.add(list);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

相关阅读:
npm install / webdriver-manager update报错 unable to get local issuer certificate
PyTorch（一）安装与环境配置
 数据驾驶舱只是面子工程？它的真正作用你根本就不了解
 ArcGIS_创建随机点
 【周末闲谈】什么是云计算？
codeforces每日5题(均1700)-第二天
 VC++父进程交互式操作子进程标准输入输出
 go-zero jwt 鉴权快速实战
 GUI编程--PyQt5--QMessageBox
java计算机毕业设计医院挂号管理系统源程序+mysql+系统+lw文档+远程调试
原文地址：https://blog.csdn.net/weixin_45565886/article/details/126331528