二叉树面试题
链表是一种动态的数据结构，因为在创建链表时，我们不需要知道链表的长度，当插入一个结点时，只需要为该结点分配内存，然后调整指针的指向来确保新结点被连接到链表中。所以，它不像数组，内存是一次性分配完毕的，而是每添加一个结点分配一次内存。正是因为这点，所以它没有闲置的内存，比起数组，空间效率更高。
1)单向链表，双向链表
单向：每个节点只有一个后继指针next指向后面的节点，结尾通常指向null
双向：包含两个指针，prev指向前一节点，next指向后一节点
2)带头链表，不带头链表
3)循环的，非循环的
循环：特殊的单链表，尾结点指向头节点
首先创建节点类：单链表中的节点应该具有两个属性：val 和 next。val存储的该节点的数据值，next存储下一个节点的地址。下面提供两种创建链表的方式：分别是枚举法和尾插法。
线性表面试题
排序面试题
图算法面试题
高频算法面试题
class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
枚举法：直接进行val的赋值以及对next的初始化。
public ListNode head;//链表的头
public void creatList(){
ListNode listNode1 = new ListNode(11);
ListNode listNode2 = new ListNode(22);
ListNode listNode3 = new ListNode(33);
ListNode listNode4 = new ListNode(44);
this.head=listNode1;
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
}
class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
尾插法：插入第一个节点时，直接将该节点赋值给head,之后每次插入新节点都会通过head.next移动到最后一个节点cur，然后将新节点赋值给cur.next。
public ListNode head;//链表的头
public void add(int data){
ListNode node = new ListNode(data);
if(this.head == null){
this.head = node;
}else {
ListNode cur = this.head;
while(cur.next != null){
cur = cur.next;
}
cur.next = node;
}
}
头结点head是不动的，通过head.next不断移动，在移动的过程中输出链表的内容。
public void display(){
ListNode cur = this.head;
while(cur != null){
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
思路：根据栈先进后出的特点，在遍历链表时，把值按顺序放入栈中，最后出栈就是逆序了。
/**
* 栈
*/
public List<Integer> printListFromQueue(ListNode listNode) {
Stack<Integer> stack = new Stack<>();
while (listNode != null) {
stack.add(listNode.value);
listNode = listNode.next;
}
List<Integer> list = new ArrayList<>();
while (!stack.isEmpty()) {
list.add(stack.pop());
}
return list;
}
思路：因为递归的本质也是用的栈，所以先递归输出它的后面节点，再输出自己，这样链表就反过来了。
/**
* 递归
*/
public List<Integer> printListFromDG(ListNode listNode) {
List<Integer> list = new ArrayList<>();
if (listNode != null) {
list.addAll(printListFromDG(listNode.next));
list.add(listNode.value);
}
return list;
}
将链表元素都赋值到数组中，然后可以从数组两端向中间对比。
将链表元素全部压栈，然后一边出栈，一边重新遍历链表，一边比较，只要有一个不相等，那就不是回文链表了。
public boolean isPalindrome(ListNode head) {
ListNode temp = head;
Stack<Integer> stack = new Stack();
//把链表节点的值存放到栈中
while (temp != null) {
stack.push(temp.val);
temp = temp.next;
}
//然后再出栈
while (head != null) {
if (head.val != stack.pop()) {
return false;
}
head = head.next;
}
return true;
}
上面方法的改造，先遍历第一遍，得到总长度。之后一遍历链表，一遍压栈。当到达链表长度一半的位置之后，就不再压栈，而是一边出栈，一遍遍历，一遍比较，只要有一个不相等，就不是回文链表。
public boolean isPalindrome(ListNode head) {
if (head == null)
return true;
ListNode temp = head;
Stack<Integer> stack = new Stack();
//链表的长度
int len = 0;
//把链表节点的值存放到栈中
while (temp != null) {
stack.push(temp.val);
temp = temp.next;
len++;
}
//len长度除以2
len >>= 1;
//然后再出栈
while (len-- >= 0) {
if (head.val != stack.pop())
return false;
head = head.next;
}
return true;
}
我们使用快慢指针 ，fast一次走两步，slow一次走一步。当fast到达表尾的时候，slow正好到达一半的位置，那么接下来可以从头开始逆序一半的元素，或者从slow开始逆序一半的元素，都可以。
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) {
return true;
}
ListNode slow = head, fast = head;
ListNode pre = head, prepre = null;
while(fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
//将前半部分链表反转
pre.next = prepre;
prepre = pre;
}
if(fast != null) {
slow = slow.next;
}
while(pre != null && slow != null) {
if(pre.val != slow.val) {
return false;
}
pre = pre.next;
slow = slow.next;
}
return true;
}
思路：循环链表将链表节点（注意是节点，不是节点里的值）存入到hashset中，如果元素添加不进去则证明有环。
public static boolean hasCycle1(ListNode head){
//存入的是ListNode类型而不是值
HashSet<ListNode> hashSet = new HashSet<>();
while (head!=null){
if (!hashSet.add(head)){
return true;
}
head=head.next;
}
return false;
}
复杂度分析：
时间复杂度：O(N)，其中 N 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。
空间复杂度：O(N)，其中 N 是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。
解决思路：定义两个指针，一个指针每次移动一个位置为慢指针，一个指针每次移动两个位置为快指针。当两个指针相遇时就证明有环，如果快指针或者慢指针下一个节点为null，则证明无环。
为什么两个指针一定会相遇呢？
两个指针一旦进入环，遍历的时候相当于无限循环因为出不出来环啊。想象一下时钟，时针分针秒针在不同速度遍历时是不是会相遇呢？
public static boolean hasCycle2(ListNode head){
if (head==null || head.next==null){
return false;
}
//定义两个指针,快指针比慢指针多一步
ListNode slow = head;
ListNode fast = head.next;
while (slow!=fast){
if (fast==null||fast.next==null){
return false;
}
//快指针比慢指针多一步
slow=slow.next;
fast=fast.next.next;
}
return true;
}
复杂度分析
时间复杂度O(N) : 当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N 轮。
空间复杂度O(1) : 只使用了两个指针额外的空间
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
思路;双指针思想
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}else{
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:输入: 1->1->2 输出: 1->2
示例 2:输入: 1->1->2->3->3 输出: 1->2->3
//一次遍历，注意边界条件。
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while(cur != null && cur.next != null){
if(cur.val == cur.next.val)
cur.next = cur.next.next;
else
cur = cur.next;
}
return head;
}
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：给定的 n 保证是有效的。
//设置哑节点1，让它走 n+1 步，再设置哑节点2，然后哑节点1和哑节点2一起移动，
//直到哑节点1走完链表，此时哑节点1和哑节点2之间正好隔着 n 个节点，再通过哑节点2删除倒数第 n 个节点。
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
for (int i = 1; i <= n + 1;i++){
first = first.next;
}
ListNode second = dummy;
while(first != null){
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:给定 1->2->3->4, 你应该返回 2->1->4->3.
//设置哑节点，注意循环条件，指针移动的速度是2（因为需要两两交换节点）。
public ListNode swapPairs (ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
while (pre.next != null && pre.next.next != null) {
ListNode l1 = pre.next;
ListNode l2 = pre.next.next;
l1.next = l2.next;
l2.next = l1;
pre.next = l2;
pre = l1;
}
return dummy.next;
}
给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例:输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出: 7 -> 8 -> 0 -> 7
//既然不能改变链表的结构（翻转链表），那就用一个栈来保存链表中的值，可以做到逆向输出。
//相加部分的代码逻辑就按常规思路写。
public ListNode addTwoNumbers (ListNode l1, ListNode l2) {
Stack<Integer> l1Stack = listNodetoStack(l1);
Stack<Integer> l2Stack = listNodetoStack(l2);
int carry = 0;
ListNode head = new ListNode(-1);
while (!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0) {
int x = l1Stack.isEmpty() ? 0 : l1Stack.pop();
int y = l2Stack.isEmpty() ? 0 : l2Stack.pop();
int sum = x + y + carry;
ListNode node = new ListNode(sum % 10);
carry = sum / 10;
node.next = head.next;
head.next = node;
}
return head.next;
}
private Stack<Integer> listNodetoStack (ListNode head) {
Stack<Integer> stack = new Stack<>();
while (head != null) {
stack.push(head.val);
head = head.next;
}
return stack;
}
给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。
每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。
这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。
返回一个符合上述规则的链表的列表。
举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]
示例 1：
输入: root = [1, 2, 3], k = 5 输出: [[1],[2],[3],[],[]] 解释: 输入输出各部分都应该是链表，而不是数组。 例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。 第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。 最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。
示例 2：
输入: root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3 输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]] 解释: 输入被分成了几个连续的部分，并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。
提示:
● root 的长度范围： [0, 1000].
● 输入的每个节点的大小范围：[0, 999].
● k 的取值范围： [1, 50].
/*思路：先统计出链表长度，除以 k, 求商和余数，其中：
● 余数代表最后结果中有多少个长链表
● 商代表每个短链表的长度（结果集中后部的链表）
● 长链表比短链表多一个节点*/
public ListNode[] splitListToParts (ListNode root, int k) {
ListNode cur = root;
int len = 0;
while (cur != null) {
cur = cur.next;
len++;
}
int mod = len % k;
int size = len / k;
cur = root;
ListNode[] ans = new ListNode[k];
for (int i = 0; cur != null && i < k; i++) {
ans[i] = cur;
int curSize = size + (mod-- > 0 ? 1 : 0);
for (int j = 0; j < curSize - 1; j++) {
cur = cur.next;
}
ListNode next = cur.next;
cur.next = null;
cur = next;
}
return ans;
}
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL
示例 2:输入: 2->1->3->5->6->4->7->NULL 输出: 2->3->6->7->1->5->4->NULL
说明:
● 应当保持奇数节点和偶数节点的相对顺序。
● 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
设置三个指针，其中奇指针和偶指针是很自然能想到的，evenHead起辅助作用，用于将奇链表和偶链表结合起来。
public ListNode oddEvenList (ListNode head) {
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
官方微信
官方抖音
京公网安备 11030102010736号