06-链表相关面试题
链表相关面试题
链表问题
面试时链表解题的方法论
1)对于笔试，不用太在乎空间复杂度，一切为了时间复杂度
2)对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法
链表面试题常用数据结构和技巧
1）使用容器(哈希表、数组等)
2）快慢指针
快慢指针
1）输入链表头节点，奇数长度返回中点，偶数长度返回上中点
2）输入链表头节点，奇数长度返回中点，偶数长度返回下中点
3）输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
4）输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
注意边界条件
- 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
// head 头
public static Node midOrUpMidNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return head;
}
// 链表有3个点或以上
Node slow = head.next;
Node fast = head.next.next;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
- 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
public static Node midOrDownMidNode(Node head) {
if (head == null || head.next == null) {
return head;
}
Node slow = head.next;
Node fast = head.next;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
- 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
public static Node midOrUpMidPreNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
Node slow = head;
Node fast = head.next.next;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
- 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
public static Node midOrDownMidPreNode(Node head) {
if (head == null || head.next == null) {
return null;
}
if (head.next.next == null) {
return head;
}
Node slow = head;
Node fast = head.next;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
常见链表面试题
题目1: 判断链表是否为回文结构
上面说了，链表常用技巧主要就是使用容器(哈希表、数组等)和快慢指针
所以有3个方法。
方法1：建栈比对
将所有节点压入栈中，然后与链表节点一一对比。
相当于逆序了，然后逆序与正序比较，相同为回文结构
public static boolean isPalindrome1(Node head) {
Stack<Node> stack = new Stack<Node>();
Node cur = head;
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
while (head != null) {
if (head.value != stack.pop().value) {
return false;
}
head = head.next;
}
return true;
}
方法2：快慢指针加建栈
使用快慢指针定位到链表中间，然后将链表右半部分建栈，一一比较。
当然偶数长度的话，就截下中点
public static boolean isPalindrome2(Node head) {
if (head == null || head.next == null) {
return true;
}
Node right = head.next;
Node cur = head;
while (cur.next != null && cur.next.next != null) {
right = right.next;
cur = cur.next.next;
}
Stack<Node> stack = new Stack<Node>();
while (right != null) {
stack.push(right);
right = right.next;
}
while (!stack.isEmpty()) {
if (head.value != stack.pop().value) {
return false;
}
head = head.next;
}
return true;
}
方法3：纯指针操作，空间复杂度O (1)
快慢指针找到链表中点。
从中点开始，将中点后面的指针指向逆序。并再将中点指向null作为终止条件。
例如：1–> 2 – >3 --> 2–> 1就变为1–> 2–> 3 <–2 <-- 1
然后将中点3，指向null，偶数长度2选一，随便中点一个指向null
指针逆序完成后。
一个head从头，一个tail从尾开始一一比较，head或tail任意一个为null时停止。
之前比较时，记录一下尾节点，因为现在恢复节点，我们就重新从尾节点开始恢复。
public static boolean isPalindrome3(Node head) {
//边界条件
if (head == null || head.next == null) {
return true;
}
Node n1 = head;
Node n2 = head;
while (n2.next != null && n2.next.next != null) { // find mid node
n1 = n1.next; // n1 -> mid
n2 = n2.next.next; // n2 -> end
}
// n1 中点
n2 = n1.next; // n2 -> right part first node
n1.next = null; // mid.next -> null
Node n3 = null;
while (n2 != null) { // right part convert
n3 = n2.next; // n3 -> save next node
n2.next = n1; // next of right node convert
n1 = n2; // n1 move
n2 = n3; // n2 move
}
// 记录n1尾节点，对比完成后，从n1开始更改会原来的指向
n3 = n1;
n2 = head;// n2 -> left first node
boolean res = true;
while (n1 != null && n2 != null) { // check palindrome
if (n1.value != n2.value) {
res = false;
break;
}
n1 = n1.next; // left to mid
n2 = n2.next; // right to mid
}
n1 = n3.next;
n3.next = null;
while (n1 != null) { // recover list
n2 = n1.next;
n1.next = n3;
n3 = n1;
n1 = n2;
}
return res;
}
题目2：链表做荷兰国旗问题
有2种方法
方法1：倒入数组做partition，然后链起来
partition，快排的核心函数
此方法只为AC，没考虑空间复杂度。
代码大体为：
先得到链表长度，然后new出相同长度的数组，并循环往数组里拷贝值。
然后将这个数组做partition。
然后将数组元素取出，链起来
public static Node listPartition1(Node head, int pivot) {
if (head == null) {
return head;
}
Node cur = head;
int i = 0;
while (cur != null) {
i++;
cur = cur.next;
}
Node[] nodeArr = new Node[i];
i = 0;
cur = head;
for (i = 0; i != nodeArr.length; i++) {
nodeArr[i] = cur;
cur = cur.next;
}
arrPartition(nodeArr, pivot);
for (i = 1; i != nodeArr.length; i++) {
nodeArr[i - 1].next = nodeArr[i];
}
nodeArr[i - 1].next = null;
return nodeArr[0];
}
public static void arrPartition(Node[] nodeArr, int pivot) {
int small = -1;
int big = nodeArr.length;
int index = 0;
while (index != big) {
if (nodeArr[index].value < pivot) {
swap(nodeArr, ++small, index++);
} else if (nodeArr[index].value == pivot) {
index++;
} else {
swap(nodeArr, --big, index);
}
}
}
public static void swap(Node[] nodeArr, int a, int b) {
Node tmp = nodeArr[a];
nodeArr[a] = nodeArr[b];
nodeArr[b] = tmp;
}
方法2：链表操作
方法2只使用了有限的几个变量
先声明6个node，分别为小于区的head(sH)，tail(sT)，等于区的head(eH)，tail(eT)，大于区的head(mH)，tail(mT)。
每个区都有两个节点，一个记录头，一个记录尾。然后对链表进行遍历比较，当前节点值小于就放入小于区。
如果小于区为空，就同时赋给sH，sT。如果小于区又来了个node，将将其链到尾节点sT下，sT.next = 新来的node。然后sT = 新来的node，保持sT一直在链表尾。
当链表遍历结束，所有节点都到了属于自己的区。于是场上便有3个区的3个链表。
我们只需要将3个链表链起来，便可以了。只不过链的时候要注意考虑判断是否存在空链表的情况。
public static Node listPartition2(Node head, int pivot) {
Node sH = null; // small head
Node sT = null; // small tail
Node eH = null; // equal head
Node eT = null; // equal tail
Node mH = null; // big head
Node mT = null; // big tail
Node next = null; // save next node
while (head != null) {
next = head.next;
head.next = null;
if (head.value < pivot) {
if (sH == null) {
sH = head;
sT = head;
} else {
sT.next = head;
sT = head;
}
} else if (head.value == pivot) {
if (eH == null) {
eH = head;
eT = head;
} else {
eT.next = head;
eT = head;
}
} else {
if (mH == null) {
mH = head;
mT = head;
} else {
mT.next = head;
mT = head;
}
}
head = next;
}
// 小于区域的尾巴，连等于区域的头，等于区域的尾巴连大于区域的头
if (sT != null) { // 如果有小于区域
sT.next = eH;
eT = eT == null ? sT : eT; // 下一步，谁去连大于区域的头，谁就变成eT
}
// 下一步，一定是需要用eT 去接 大于区域的头
// 有等于区域，eT -> 等于区域的尾结点
// 无等于区域，eT -> 小于区域的尾结点
// eT 尽量不为空的尾巴节点
if (eT != null) { // 如果小于区域和等于区域，不是都没有
eT.next = mH;
}
return sH != null ? sH : (eH != null ? eH : mH);
}
题目3: 深度复制带有rand指针的链表
题目如下：
LeetCode题目连接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/
—种特殊的单链表节点类描述如下：
public class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
random指针是单链表节点结构中新增的指针，random可能指向链表中的任意一个节点，也可能指向null。
给定一个由Node节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
【要求】时间复杂度O(N)．额外空间复杂度O(1)
此问题依然有两个方法，依靠HashMap的数据结构和纯指针操作
方法1：HashMap
将链表节点复制，并放到HashMap中。key为原链表的老节点，value为复制的新节点。
然后我们可以去遍历链表，
通过map，去找到key的next，赋给对应value的next，key的rand赋给value的rand。
循环结束，复制完成。
public static Node copyRandomList1(Node head) {
// key 老节点
// value 新节点
HashMap<Node, Node> map = new HashMap<Node, Node>();
Node cur = head;
while (cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
while (cur != null) {
// cur 老
// map.get(cur) 新
// 新.next -> cur.next克隆节点找到
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
方法2：链表构建对应关系
方法1，是通过hashmap构建对应关系，进行复制。而我们可以在链表上直接进行操作，构建对应关系。
思路为：
将每个节点复制，连接到对应节点后
如1–>2–>3–>4–>5，复制并链接就成为 1–>1’–>2–>2’–>3–>3’–>4–>4’–>5–>5’ (带 ’ 的为复制的节点)
这样也构建了对应关系，我们可以一对一对的取出进行操作。
例如1的rand节点指向3，那么1’就应该指向3’，因为其相邻，即：1’.rand==1.rand.next。
循环构建完对应的rand节点后。
我们便可以对链表进行分离操作
public static Node copyRandomList2(Node head) {
if (head == null) {
return null;
}
Node cur = head;
Node next = null;
// 1 -> 2 -> 3 -> null
// 1 -> 1' -> 2 -> 2' -> 3 -> 3'
while (cur != null) {
next = cur.next;
cur.next = new Node(cur.val);
cur.next.next = next;
cur = next;
}
cur = head;
Node copy = null;
// 1 1' 2 2' 3 3'
// 依次设置 1' 2' 3' random指针
while (cur != null) {
next = cur.next.next;
copy = cur.next;
copy.random = cur.random != null ? cur.random.next : null;
cur = next;
}
Node res = head.next;
cur = head;
// 老 新 混在一起，next方向上，random正确
// next方向上，把新老链表分离
while (cur != null) {
next = cur.next.next;
copy = cur.next;
cur.next = next;
copy.next = next != null ? next.next : null;
cur = next;
}
return res;
}
题目4: 两个可能有环的单链表相交的第一个节点
此问题有几种可能：
1.两个无环链表是否相交，找相交节点。不相交，返回null
2.两个有环链表，找相交节点。不相交，返回null
3.如果一个是有环链表，一个是无环链表。不用判断，这两个链表必不相交。
准备操作，判断链表是否有环，返回入环节点
在对上面3中可能进行操作前，首先我们需要有一个能判断链表是否有环的方法。
并返回入环节点。
通过快慢指针实现，slow和fast指针，slow一次走一步，fast一次走两步。
当slow与fast相遇时。
fast回到链表头，slow依然呆在相遇点。
然后fast，slow再次一起移动，不过这次两者都是一次走一步。
然后两者再次相遇时，便是入环点。
// 找到链表第一个入环节点，如果无环，返回null
public static Node getLoopNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
// n1 慢 n2 快
Node slow = head.next; // n1 -> slow
Node fast = head.next.next; // n2 -> fast
while (slow != fast) {
if (fast.next == null || fast.next.next == null) {
return null;
}
fast = fast.next.next;
slow = slow.next;
}
// slow fast 相遇
fast = head; // n2 -> walk again from head
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
然后先看第一种，两个无环链表
大致思路为：
先声明一个int数，用来记录2个链表长度的差值。
将2个链表分别遍历，一个n++，一个n–，最后n的值，就是两个链表长度的差值。
2个链表都遍历到尾部，我们先比较尾部节点，如果不相等，则不相交，直接返回。
如果相等，则相交，继续操作找出相交点。
选择较长的一个链表，先走n（长度差）步。然后2个链表同时++，进行移动。
当2个节点相等，即是相交点。
// 如果两个链表都无环，返回第一个相交节点，如果不想交，返回null
public static Node noLoop(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
Node cur1 = head1;
Node cur2 = head2;
int n = 0;
while (cur1.next != null) {
n++;
cur1 = cur1.next;
}
while (cur2.next != null) {
n--;
cur2 = cur2.next;
}
if (cur1 != cur2) {
return null;
}
// n : 链表1长度减去链表2长度的值
cur1 = n > 0 ? head1 : head2; // 谁长，谁的头变成cur1
cur2 = cur1 == head1 ? head2 : head1; // 谁短，谁的头变成cur2
n = Math.abs(n);
while (n != 0) {
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
两个有环链表
如果是两个有环链表，找向交点，存在3种情况。
1.两个有环链表不相交
2.两个有环链表相交，且入环点相同
3.两个有环链表相交，但入环点不相同。
首先解决情况2，入环点相同。
如果入环点相同，我们可以将入环点设为end截止，然后用上面noLoop的方式去找相交点。
情况1和情况3，可以一起解决。
随便用一个入环点，循环一次，去找另一个入环点，找到了，直接返回。没找到则是没相交
//参数loop为入环点
public static Node bothLoop(Node head1, Node loop1, Node head2, 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);
while (n != 0) {
n--;
cur1 = cur1.next;
}
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;
}
}
调用方法
上面写了3个方法，我们需要一个方法进行整合
先获取两个链表的入环点
如果都没环，进行noLoop判断
如果有环，进行bothLoop判断。
如果一个有环，一个没环，直接return 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 noLoop(head1, head2);
}
if (loop1 != null && loop2 != null) {
return bothLoop(head1, loop1, head2, loop2);
}
return null;
}
题目5: 不给单链表的头节点删除指定节点
此问题如标题所示：
一个单链表，不给头节点。只给要删除的节点，让你删除。
有个取巧的方法，可以把删除节点的下一个节点的值，覆盖要删除的值，然后删除下一个节点。
但这种方法并不是真正的删除。
实际上，不给单链表的头节点删除指定节点的操作，是不可能的。
要删除就要给头节点。