引言
在上篇文章數(shù)據結構與算法之鏈表(二)單鏈表的基本實現(xiàn)中我們學習了單鏈表的基本概念,本篇我們在此基礎之上研究單鏈表相對復雜的操作(也是面試中經常被問到的經典問題，這是其次亮蛔，重點是學習思想)寺晌。本文的代碼都是基于上篇單鏈表而實現(xiàn)的丧靡。
單鏈表的逆序實現(xiàn)
整體思路:鏈表的逆序過程必然會將鏈表分割成兩個部分:原鏈表和已經逆序好的鏈表,那么逆序操作的起始點可以從表頭或者表尾開始综膀；
單鏈表的逆序實現(xiàn)(表頭開始)
1.思路:既然原始單鏈表被分割成兩部分,加入當前需要將節(jié)點curNode加入逆序鏈表，必然需要記錄p的后繼節(jié)點以便下個節(jié)點的逆序操作葛躏，還需要一個節(jié)點reversHead指向已經逆序的鏈表,引入nextNode保存curNode下個操作節(jié)點;這樣每一次針對curNode的逆序操作如下:
1>操作節(jié)點后繼指向逆序列表頭(操作節(jié)點做斷裂操作);
2>逆序列表頭更新為當前操作節(jié)點(操作節(jié)點做連接逆序鏈表操作)澈段；
3> 本次逆序操作結束,curNode指向下個節(jié)點。
代碼如下:
/**
* 單鏈表的逆序操作(從表頭非遞歸)
*/
public void reverseList() {
//逆序操作只有在2個元素以上才有效
if (isEmpty() || headNode.next == null) {
return;
}
SNode<T> curNode = headNode;//當前要逆序操作的節(jié)點
SNode<T> reversHead = null;//當前的逆序頭節(jié)點
while (curNode != null) {
SNode<T> nextNode = curNode.next;//保存下個操作節(jié)點
curNode.next = reversHead;//操作節(jié)點指向逆序列表頭,做斷裂操作
reversHead = curNode;//逆序列表頭更新,操作節(jié)點做連接操作
curNode = nextNode;//下個節(jié)點
}
headNode = reversHead;
}
單鏈表的逆序實現(xiàn)(表尾開始)
思路:從表尾開始逆序舰攒，每次的遞歸操作如下:
1> 遍歷已經逆序好的鏈表到結尾败富，掛載當前操作節(jié)點到逆序鏈表上；
2>掛載的節(jié)點做原鏈表斷開操作;
3>當操作節(jié)點為原鏈表的尾部節(jié)點時摩窃，直接返回該節(jié)點當做逆序鏈表的頭節(jié)點兽叮。代碼如下:
/**
* 遞歸逆序鏈表,
*
* @param p 當前需要逆序的操作節(jié)點
* @return 逆序后的鏈表頭節(jié)點
*/
private SNode<T> reverseNodeRecursion(SNode<T> p) {
if (p.next == null) {//遞歸結束條件芬骄，從鏈表尾開始逆序操作
return p;//直接返回尾部節(jié)點當做逆序鏈表的起點
} 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;//當前節(jié)點已經掛載，則斷開與原鏈表的聯(lián)系
return result;
}
}
查找中間節(jié)點
思路:采用兩個指針:快指針和慢指針鹦聪，快指針移速是慢指針的兩倍账阻，當快指針達到結尾，慢指針正好到達中間位置.
/**
* 查找中間節(jié)點,快節(jié)點掃描速度是慢節(jié)點兩倍
*
* @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;
}
查找倒數(shù)第K個元素
思路:采用兩個指針:前指針和后指針泽本，前指針先移動K步淘太，然后同時移動，當前指針到達結尾规丽，則后指針為目標位置蒲牧。
/**
* 查找倒數(shù)第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;
}
//右邊的掃描節(jié)點到結尾
while (rightNode != null && rightNode.next != null) {
rightNode = rightNode.next;
leftNode = leftNode.next;
}
return leftNode.data;
}
基本排序
思路:雙層循環(huán)進行兩兩交換。
/**
* 基本排序
*/
public void sortList() {
if (isEmpty()) {
return;
}
SNode<T> curNode = headNode;
while (curNode.next != null) {//大循環(huán)
//小循環(huán)
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;
}
}
刪除重復元素
思路:雙層循環(huán)進行刪除元素操作赌莺，注意操作的節(jié)點是當前節(jié)點的后繼節(jié)點造成。
/**
* 刪除重復元素,類似排序，需要嵌套遍歷
*/
public void removeAllDuplicateItems() {
SNode<T> curNode = headNode;//大循環(huán)
while (curNode != null) {
SNode<T> temp = curNode;
while (temp.next != null) {//由于要做刪除操作雄嚣，所以需要它的前驅晒屎，這里操作節(jié)點為temp.next
if (temp.next.data.equals(curNode.data)) {//如果相等則做刪除操作
//刪除操作
temp.next = temp.next.next;//刪除temp.next節(jié)點
} else {
temp = temp.next;//否則下個節(jié)點
}
}
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());
}
}
以上就是單鏈表的常用操作缓升，除了這些鼓鲁，還有一個比較經典的單鏈表尾環(huán)問題，這個問題涉及數(shù)學中的跑道追及問題港谊，限于篇幅骇吭，在下一篇將做全面細致的分析。
