引言
在上篇文章数据结构与算法之链表(二)单链表的基本实现中我们学习了单链表的基本概念,本篇我们在此基础之上研究单链表相对复杂的操作(也是面试中经常被问到的经典问题，这是其次，重点是学习思想)。本文的代码都是基于上篇单链表而实现的。
单链表的逆序实现
整体思路:链表的逆序过程必然会将链表分割成两个部分:原链表和已经逆序好的链表,那么逆序操作的起始点可以从表头或者表尾开始；
单链表的逆序实现(表头开始)
1.思路:既然原始单链表被分割成两部分,加入当前需要将节点curNode加入逆序链表，必然需要记录p的后继节点以便下个节点的逆序操作，还需要一个节点reversHead指向已经逆序的链表,引入nextNode保存curNode下个操作节点;这样每一次针对curNode的逆序操作如下:
1>操作节点后继指向逆序列表头(操作节点做断裂操作);
2>逆序列表头更新为当前操作节点(操作节点做连接逆序链表操作)；
3> 本次逆序操作结束,curNode指向下个节点。
代码如下:
/**
* 单链表的逆序操作(从表头非递归)
*/
public void reverseList() {
//逆序操作只有在2个元素以上才有效
if (isEmpty() || headNode.next == null) {
return;
}
SNode<T> curNode = headNode;//当前要逆序操作的节点
SNode<T> reversHead = null;//当前的逆序头节点
while (curNode != null) {
SNode<T> nextNode = curNode.next;//保存下个操作节点
curNode.next = reversHead;//操作节点指向逆序列表头,做断裂操作
reversHead = curNode;//逆序列表头更新,操作节点做连接操作
curNode = nextNode;//下个节点
}
headNode = reversHead;
}
单链表的逆序实现(表尾开始)
思路:从表尾开始逆序，每次的递归操作如下:
1> 遍历已经逆序好的链表到结尾，挂载当前操作节点到逆序链表上；
2>挂载的节点做原链表断开操作;
3>当操作节点为原链表的尾部节点时，直接返回该节点当做逆序链表的头节点。代码如下:
/**
* 递归逆序链表,
*
* @param p 当前需要逆序的操作节点
* @return 逆序后的链表头节点
*/
private SNode<T> reverseNodeRecursion(SNode<T> p) {
if (p.next == null) {//递归结束条件，从链表尾开始逆序操作
return p;//直接返回尾部节点当做逆序链表的起点
} else {
SNode<T> result = reverseNodeRecursion(p.next);
SNode<T> temp = result;
//找到当前逆序链表的结尾然后把p挂上去
while (temp.next != null) {
temp = temp.next;
}
temp.next = p;
p.next = null;//当前节点已经挂载，则断开与原链表的联系
return result;
}
}
查找中间节点
思路:采用两个指针:快指针和慢指针，快指针移速是慢指针的两倍，当快指针达到结尾，慢指针正好到达中间位置.
/**
* 查找中间节点,快节点扫描速度是慢节点两倍
*
* @return
*/
public T searchMid() {
if (isEmpty()) {
return null;
}
SNode<T> slowNode = headNode;
SNode<T> fastNode = headNode;
while (fastNode != null && fastNode.next != null && fastNode.next.next != null) {
slowNode = slowNode.next;
fastNode = fastNode.next.next;
}
return slowNode.data;
}
查找倒数第K个元素
思路:采用两个指针:前指针和后指针，前指针先移动K步，然后同时移动，当前指针到达结尾，则后指针为目标位置。
/**
* 查找倒数第K个元素
*
* @param k
* @return
*/
public T searchBackwardsElement(int k) {
if (isEmpty()) {
return null;
}
if (k >= size()) {
return null;
}
SNode<T> leftNode = headNode;
SNode<T> rightNode = leftNode;
for (int i = 0; i < k; i++) {
rightNode = rightNode.next;
}
//右边的扫描节点到结尾
while (rightNode != null && rightNode.next != null) {
rightNode = rightNode.next;
leftNode = leftNode.next;
}
return leftNode.data;
}
基本排序
思路:双层循环进行两两交换。
/**
* 基本排序
*/
public void sortList() {
if (isEmpty()) {
return;
}
SNode<T> curNode = headNode;
while (curNode.next != null) {//大循环
//小循环
SNode<T> tempNode = curNode.next;
while (tempNode != null) {
if (curNode.data.compareTo(tempNode.data) > 0) {
T tempData = curNode.data;
curNode.data = tempNode.data;
tempNode.data = tempData;
}
tempNode = tempNode.next;
}
curNode = curNode.next;
}
}
删除重复元素
思路:双层循环进行删除元素操作，注意操作的节点是当前节点的后继节点。
/**
* 删除重复元素,类似排序，需要嵌套遍历
*/
public void removeAllDuplicateItems() {
SNode<T> curNode = headNode;//大循环
while (curNode != null) {
SNode<T> temp = curNode;
while (temp.next != null) {//由于要做删除操作，所以需要它的前驱，这里操作节点为temp.next
if (temp.next.data.equals(curNode.data)) {//如果相等则做删除操作
//删除操作
temp.next = temp.next.next;//删除temp.next节点
} else {
temp = temp.next;//否则下个节点
}
}
curNode = curNode.next;
}
}
递归逆序打印
思路:先递归调用，再打印当前元素
/**
* 递归逆序打印
*/
public void printListReversely() {
printListReversely(headNode);
}
/**
* 逆序打印元素
* @param head
*/
public void printListReversely(SNode<T> head) {
if (head != null) {
printListReversely(head.next);
Log.e("SingleList", head.data.toString());
}
}
以上就是单链表的常用操作，除了这些，还有一个比较经典的单链表尾环问题，这个问题涉及数学中的跑道追及问题，限于篇幅，在下一篇将做全面细致的分析。
