牛客网经典Java面试常见题

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

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

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

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

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

二、从尾到头打印链表

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

输入一个长度为 n 整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

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
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

四、删除链表的节点

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

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

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

五、 只出现一次的数字

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

public int singleNumber(int[] nums) {
        int x = 0;
        for(int i = 0;i < nums.length;i++) {
            x ^= nums[i];
        }
        return x;
    }
1
2
3
4
5
6
7

方法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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18