经典Java面试常见题

小灰灰 2023-09-27 12:07 146阅读 0赞

![在这里插入图片描述][1127b99e7f1a4fe1a14253599e022188.gif_pic_center]

想必大部分人都用过PostMan软件，最近接触到一个很好用的软件:**Apifox**  
Apifox = Postman + Swagger + Mock + JMeter  
[戳我下载，推荐][Link 1]

#### 文章目录 ####

*  一、二叉搜索树与双向链表
 *  二、从尾到头打印链表
 *  三、调整数组奇数位于偶数前面
 *  四、删除链表的节点
 *  五、 只出现一次的数字

## 一、二叉搜索树与双向链表 ##

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示  
![在这里插入图片描述][3dfc799be6a743eea7b927a7821d383b.png]  
注意:  
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继  
2.返回链表中的第一个节点的指针  
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构  
4.你不用输出双向链表，程序会根据你的返回值自动打印输出

![在这里插入图片描述][d4a3e03bb76b4509a5f5df907fa9f534.png]

public class Solution {
        
        public TreeNode Convert(TreeNode pRootOfTree) {
        
           if(pRootOfTree == null) {
        
               return null;
           }
           createLinkedList(pRootOfTree);
           while(pRootOfTree.left != null) {
        
               pRootOfTree = pRootOfTree.left;
           }
           return pRootOfTree;
        }
        TreeNode prev = null;
        public  void createLinkedList(TreeNode pRootOfTree) {
        
            if(pRootOfTree == null) {
        
                return;
            }
            createLinkedList(pRootOfTree.left);
            pRootOfTree.left = prev;
            if(prev != null) {
        
                prev.right = pRootOfTree;
            }
            prev = pRootOfTree;
            createLinkedList(pRootOfTree.right);
        }
    }

## 二、从尾到头打印链表 ##

输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。  
题目地址:[从尾到头打印链表][Link 2]  
![在这里插入图片描述][182b3cbb223345b8938a063b9848f209.png]

![在这里插入图片描述][7b65aacfc6e4484ca43da0da152cf9d8.png]

import java.util.ArrayList;
    public class Solution {
        
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        
            ArrayList<Integer> list = new ArrayList<Integer>();
            if(listNode == null) {
        
                return list;
            }
            ListNode cur = listNode.next;
            listNode.next = null;
            while(cur != null) {
        
                ListNode curNext = cur.next;
                cur.next = listNode;
                listNode = cur;
                cur = curNext;
            }
            while(listNode != null) {
        
                list.add(listNode.val);
                listNode = listNode.next;
            }
            return list;
        }
    }

## 三、调整数组奇数位于偶数前面 ##

输入一个长度为 n 整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。  
![在这里插入图片描述][acad2df485644fc38c9b34567fa8b599.png]  
![在这里插入图片描述][bc44721264d34b4bac2909142609e904.png]

public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param array int整型一维数组 
         * @return int整型一维数组
         */
        public int[] reOrderArray (int[] array) {
        
            int[] arr = new int[array.length];
            int k = 0;
            for(int i = 0;i < array.length;i++) {
        
                if(array[i] % 2 == 1) {
        
                    arr[k++] = array[i];
                }
            }
            for(int i = 0;i < array.length;i++) {
        
                if(array[i] % 2 == 0) {
        
                    arr[k++] = array[i];
                }
            }
            return arr;
        }
    }

## 四、删除链表的节点 ##

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。

1.此题对比原题有改动  
2.题目保证链表中节点的值互不相同  
3.该题只会输出返回的链表和结果做对比，所以若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点  
题目地址:[从尾到头打印链表][Link 2]  
![在这里插入图片描述][abf2446ba622466e80a32f8323eed1f6.png]  
![在这里插入图片描述][be5361cb11f44e198f1df270f2bb0c4f.png]

public ListNode deleteNode (ListNode head, int val) {
        
            if(head == null) {
        
                return head;
            }
            if(head.val == val) {
        
                return head.next;
            }
            ListNode fast = head.next;
            ListNode slow = head;
            while(fast != null) {
        
                if(fast.val == val) {
        
                    slow.next = fast.next;
                    break;
                }else {
        
                    slow = slow.next;
                    fast = fast.next;
                }
            }
            return head;
        }

## 五、 只出现一次的数字 ##

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。  
**方法1 ： 异或**

public int singleNumber(int[] nums) {
        
            int x = 0;
            for(int i = 0;i < nums.length;i++) {
        
                x ^= nums[i];
            }
            return x;
        }

**方法2: HashSet**

class Solution {
        
        public int singleNumber(int[] nums) {
        
            HashSet<Integer> hashSet = new HashSet<>();
            for (int i = 0; i < nums.length; i++) {
        
                if(hashSet.contains(nums[i])) {
        
                    hashSet.remove(nums[i]);
                }else {
        
                    hashSet.add(nums[i]);
                }
            }
            for (int i = 0; i < nums.length; i++) {
        
                if(hashSet.contains(nums[i])) {
        
                    return nums[i];
                }
            }
            return -1;
        }
    }

[1127b99e7f1a4fe1a14253599e022188.gif_pic_center]: https://img-blog.csdnimg.cn/1127b99e7f1a4fe1a14253599e022188.gif#pic_center
[Link 1]: http://apifox.cn/a103aoye
[3dfc799be6a743eea7b927a7821d383b.png]: https://img-blog.csdnimg.cn/3dfc799be6a743eea7b927a7821d383b.png
[d4a3e03bb76b4509a5f5df907fa9f534.png]: https://img-blog.csdnimg.cn/d4a3e03bb76b4509a5f5df907fa9f534.png
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_bhsf_jzsf
[182b3cbb223345b8938a063b9848f209.png]: https://img-blog.csdnimg.cn/182b3cbb223345b8938a063b9848f209.png
[7b65aacfc6e4484ca43da0da152cf9d8.png]: https://img-blog.csdnimg.cn/7b65aacfc6e4484ca43da0da152cf9d8.png
[acad2df485644fc38c9b34567fa8b599.png]: https://img-blog.csdnimg.cn/acad2df485644fc38c9b34567fa8b599.png
[bc44721264d34b4bac2909142609e904.png]: https://img-blog.csdnimg.cn/bc44721264d34b4bac2909142609e904.png
[abf2446ba622466e80a32f8323eed1f6.png]: https://img-blog.csdnimg.cn/abf2446ba622466e80a32f8323eed1f6.png
[be5361cb11f44e198f1df270f2bb0c4f.png]: https://img-blog.csdnimg.cn/be5361cb11f44e198f1df270f2bb0c4f.png