1. 概述
前面的文章说到了一种很基础的数据结构——链表:数据结构与算法——链表,今天就来看看关于单链表的几种常见的操作,技术笔试的时候很大概率能够遇到其中的一些。多练习一下,对我们理解链表有很大的帮助,也能够提升我们的编码能力。废话不多说,这几个练习题是:
单链表反转
合并两个有序链表
检测链表中的环
删除链表倒数第 k 个节点
找到链表的中间节点
2. 单链表反转
单链表反转,顾名思义,就是将链表的指针指向全部倒过来,尾结点变成头节点,头节点变成尾结点。具体的代码如下:
public class SingleLinkedList {
private Node head = null;// 链表的头节点
public Node reverse(Node node) {
Node head = null;
Node previous = null;
Node current = node;
while(current != null) {
Node next = current.next;
if (next == null) {
head = current;
}
current.next = previous;
previous = current;
current = next;
}
this.head = head;
return this.head;
}
}
3. 合并两个有序链表
假如链表中存储的数据是数值类型,并且是有序的,这时候可以合并两个有序的链表,主要涉及到两个链表元素的比较。代码如下:
// 合并两个有序的链表
public Node mergeSortedList(Node la, Node lb) {
if(la == null && lb == null) return null;
if(la == null) return lb;
if(lb == null) return la;
Node p = la;
Node q = lb;
Node head = null;
// 比较第一个元素
if(p.getData() < q.getData()) {
head = p;
p = p.next;
}else {
head = q;
q = q.next;
}
// 比较后面的元素
Node r = head;
while(p != null && q != null) {
if(p.getData() < q.getData()) {
r.next = p;
p = p.next;
}else {
r.next = q;
q = q.next;
}
r = r.next;
}
// 比较链表可能剩余的元素
while(p != null) {
r.next = p;
p = p.next;
r = r.next;
}
while(q != null) {
r.next = q;
q = q.next;
r = r.next;
}
return head;
}
4. 检测链表中的环
单链表中有可能存在像循环链表这样的环形结构,检测链表中是否有这样的结构,可以利用这样的思路:定义两个指针,一个指针每次移动两个节点,另一个指针移动一个节点,如果两个指针相遇,则说明存在环,代码如下:
// 检测链表中的环
public boolean checkCircle(Node node) {
if(node == null) return false;
Node fast = node.next;
Node slow = node;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) return true;
}
return false;
}
5. 删除链表倒数第 k 个节点
这个题在笔试当中非常常见,解决的思路比较的巧妙,不容易想到,但是只要一想到,代码写起来就很简单了。主要的思路是这样的:定义一个指针 fast,从链表头开始,移动 k-1 个节点,再定义一个指针 slow,同时移动 fast 和 slow,当 fast 到达链表尾节点的时候,slow 所指向的节点就是要删除的节点。具体的代码实现如下:
public static Node deleteLastKth(Node head, int k) {
Node fast = head;
int i = 1;
// 先让前面的指针移动 k – 1 步
while(fast != null && i < k) {
fast = fast.next;
++ i;
}
Node slow = head;
Node prev = null;
// 前后指针同时移动
while(fast.next != null) {
fast = fast.next;
prev = slow;
slow = slow.next;
}
if(prev == null) {// 说明删除的是第一个节点
head = head.next;
}else {
prev.next = prev.next.next;
}
return head;
}
6. 找到链表的中间节点
寻找链表中间的那个节点,思路很简单,也是定义两个指针,一个指针每次移动两个节点,另一个指针移动一个节点,前面的指针到达链表尾部的时候,后面的指针指向的节点就是中间的那个节点:
public static Node findMiddleNode(Node head) {
if(head == null) return null;
Node fast = head;
Node slow = head;
while(fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}