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

青旅半醒 2024-04-08 08:27 18阅读 0赞

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

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

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

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

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

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

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

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