牛客网经典Java面试常见题

个人主页：熬夜磕代码丶
作品专栏: 数据结构与算法
我变秃了，也变强了
给大家介绍一款程序员必备刷题平台——牛客网
点击注册一起刷题收获大厂offer吧

文章目录

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

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
4.你不用输出双向链表，程序会根据你的返回值自动打印输出

publicclassSolution{publicTreeNodeConvert(TreeNode pRootOfTree){if(pRootOfTree ==null){returnnull;}createLinkedList(pRootOfTree);while(pRootOfTree.left !=null){
           pRootOfTree = pRootOfTree.left;}return pRootOfTree;}TreeNode prev =null;publicvoidcreateLinkedList(TreeNode pRootOfTree){if(pRootOfTree ==null){return;}createLinkedList(pRootOfTree.left);
        pRootOfTree.left = prev;if(prev !=null){
            prev.right = pRootOfTree;}
        prev = pRootOfTree;createLinkedList(pRootOfTree.right);}}

二、从尾到头打印链表

输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。
题目地址:从尾到头打印链表

importjava.util.ArrayList;publicclassSolution{publicArrayList<Integer>printListFromTailToHead(ListNode listNode){ArrayList<Integer> list =newArrayList<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 整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

publicclassSolution{/**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */publicint[] reOrderArray (int[] array){int[] arr =newint[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 被删除的节点
题目地址:从尾到头打印链表

publicListNode 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 ： 异或

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

方法2: HashSet

classSolution{publicintsingleNumber(int[] nums){HashSet<Integer> hashSet =newHashSet<>();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;}}