单链表经典面试题
1. 求单链表中有效节点的个数
思路:直接遍历节点个数即可,如果带头节点则不统计头节点
方法代码:
/**
* 遍历求链表有效节点个数,但不统计头节点
* @param head 传入头节点
* @return 返回有效节点个数
*/
public int getLength(Node head) {
// 判断是否为空
if (head.next == null) {
return 0;
}
Node temp = head;
int length = 0;
while (temp.next != null) {
length++;
temp = temp.next;
}
return length;
}
2. 查找单链表中的倒数第k个节点
思路:要求只能遍历一次链表,利用双指针。
- 定义front和rear两个快慢指针,初始时都指向headNode;
- 求倒数第k个节点,front快指针先走k步;
- 之后front和rear同时向后遍历,当front走到链表尾部时停止,此时rear所指的节点即为要找的倒数第k个节点。
/**
* 利用双指针,仅遍历一次找到链表的倒数第k个节点
* @param head 传入头节点
* @param index 传入的k值
* @return 返回找到的倒数第k个节点
*/
public Node findLastIndexNode(Node head, int index) {
if (head.next == null) { // 判断链表是否为空
return null;
}
// 校验index,index值应为正值且不能大于链表长度
int size = getLength(head);
if (index <= 0 || index > size) return null;
// 定义快慢两个指针
Node front = head;
Node rear = head;
// 快指针先走index步
for (int i = 0; i < index; i++) {
front = front.next;
}
// 遍历至链表尾部
while (front != null) {
front = front.next;
rear = rear.next;
}
return rear;
}
3. 单链表的反转
两种思路:
- 单链表的"头插法"
- 先定义一个新节点reverseHead当作新链表的头节点;
- 遍历原来的链表,并定义curNode和nextNode用于记录当前遍历的节点及其下一个节点,保证链表不断开;
- 每遍历一个curNode,就将其从原链表取出,放入新链表的头节点reverseHead之后;
- 令head.next = reverseHead.next,也即让原链表的头节点的next域指向新链表reverseHead的下一个节点,即反转后的链表替换掉了已经为空的原链表。
/**
* 利用单链表的“头插法”的思想反转链表
* @param head 传入原链表的头节点
*/
public void reverseList(Node head) {
// 判断链表是否为空 || 链表只有一个有效节点,则不需要反转,直接return
if (head.next == null || head.next.next == null) return;
// 定义一个新的节点作为新链表的头节点
Node reverseHead = new Node(0);
// 定义两个辅助变量,cur指向原链表遍历时的当前节点,next用于记录cur的下一个节点
Node curNode = head.next;
Node nextNode = null;
while (curNode != null) {
// 每次遍历前先记录nextNode,防止cur取出后原链表断开丢失位置
nextNode = curNode.next;
// 将curNode与新链表建立连接
curNode.next = reverseHead.next;
reverseHead.next = curNode;
// 后移
curNode = nextNode;
}
// 将新链表接入原链表完成反转
head.next = reverseHead.next;
}
- 原地反转
- 原地反转与“头插法”的思路类似,但区别在于,原地反转直接对原链表修改,不建立新的链表;
- 同样需要定义两个辅助变量preNode和curNode分别用于记录当前遍历的节点及其前一个节点;
- 初始状态下,preNode = head.next,curNode = preNode.next;
- 将curNode从原链表中取出,即preNode.next指向原来curNode的下一个节点,并将其转而添加到头节点之后(即链表头处);
- 由于原本的curNode已完成反转,继续向后遍历时preNode不动,新的curNode = preNode.next。
/**
* 就地反转链表,与“头插法”思想类似,将curNode插入到head头节点之后,但不创建新链表
* @param head 传入头节点
*/
public void localReverseList(Node head) {
// 判断链表是否为空 || 链表只有一个有效节点,则不需要反转,直接return
if (head.next == null || head.next.next == null) return;
Node preNode = head.next;
Node curNode = preNode.next;
while (curNode != null) {
// 取出curNode,让preNode与后续节点建立联系
preNode.next = curNode.next;
// 将curNode插入到链表头,即head节点之后
curNode.next = head.next;
head.next = curNode;
// 新的curNode后移
curNode = preNode.next;
}
}
4. 从尾到头打印单链表
两种思路:
- 方式一:先将单链表反转,然后再遍历。但题目要求仅要求逆序打印,反转会破坏原来单链表的结构,这样实现后若要求再次顺序打印就会有问题。
- 方式二:利用栈这个数据结构。将各个节点压入栈中,然后利用栈的先入后出的特点来实现逆序打印。
/**
* 利用栈逆序打印单链表,不破坏原来的链表结构
* @param head 传入头节点
*/
public void reversePrint (Node head) {
// 判空
if (head.next == null) return;
Node temp = head.next;
// 创建一个栈
Stack<Node> stack = new Stack<>();
// 遍历链表,将节点压入栈中
while (temp != null) {
stack.push(temp);
temp = temp.next;
}
// 将节点依次从栈顶弹出
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
5. 合并两个有序的单链表,使得合并之后的链表依然有序
/**
* 合并两个有序链表
* @param head1 传入第一个链表的头节点
* @param head2 传入第二个链表的头节点
* @return 返回合并后的新链表的头节点
*/
public Node mergeTwoLists(Node head1, Node head2) {
// 先判断边界值,两链表为空的情况
if (head1.next == null) return head2;
if (head2.next == null) return head1;
// 创建一个新的头节点,以及一个辅助变量temp
Node newHead = new Node(0);
Node temp = newHead;
// 当两个链表都仍在遍历有效值时
while (head1.next != null && head2.next != null) {
// 判断分别在两链表当前位置的节点value,哪个更小temp就指向谁
if (head1.next.value < head2.next.value) {
temp.next = head1.next;
// 不断移动temp以及两链表遍历的当前节点
temp = temp.next;
head1.next = head1.next.next;
}else {
temp.next = head2.next;
temp = temp.next;
head2.next = head2.next.next;
}
}
// 当有一个链表遍历到空值时退出循环,
// 此时将另一个还未遍历完全的链表的剩余节点直接接入到temp后,即拼接到新链表之后
if (head1.next == null) {
temp.next = head2.next;
}
if (head2.next == null) {
temp.next = head1.next;
}
return newHead;
}
标签:Node,面试题,单链,head,next,链表,经典,curNode,节点
From: https://www.cnblogs.com/SnkrGao/p/17204329.html