說兩句
單鏈表是一種基本的數(shù)據(jù)結構,也是現(xiàn)在技術面試經(jīng)沉嫖ǎ考到東西(我曾在這跌倒過,那叫個慘,誰讓我們平時并不注重這些基本算法呢),所以呢,身為技術人員,還是要多看看這些數(shù)據(jù)算法,萬一哪天我們都成為大神呢,哈哈哈!
單鏈表反轉
1. 遞歸思想
遞歸思想,
重點問題一:在于找出遞歸退出點,顯然單鏈表反轉退出點在于尾節(jié)點的nex節(jié)點為null的判斷上
重點問題二:遞歸過程中處理邏輯.遞歸思想每次處理的都是關聯(lián)的兩個元素,其實反轉的重點思想在于將原有下級元素的next設置為它的父節(jié)點,而它的父節(jié)點會在遞歸的下次后將處理它的下一個節(jié)點的反轉邏輯.
總結如下圖,每次遞歸返回當前節(jié)點保存了它下一個節(jié)點的引用,然后反轉本節(jié)點和下一個節(jié)點,本節(jié)點置為尾節(jié)點,以此類推:
遞歸反轉單鏈表.png
核心代碼如下:
public static Node reverser(Node root){
//1.跳出條件
if(root ==null||root.getNext()==null){
return node;
}
//2. 遞歸調用,直到最后節(jié)點
Node next=reverser(root.getNext());
//3. 遞歸每步進行逐步反轉
root.getNext().setNext(root);
root.setNext(null);
//4. 返回新的尾節(jié)點
return next;
}
// 2. 三指針循環(huán)法
關鍵點:
- 解決循環(huán)反轉過程中斷鏈問題
- 三個指針后移,避免死循環(huán)問題
總結如下圖,利用三個起始位置不同的指針,兩個臨時變量逐步后移,當出現(xiàn)斷鏈時,通過第三個指針不斷續(xù)接.
三指針反轉.png
代碼:
/**
* 循環(huán)進行反轉
*/
public static Node reverser1(Node node) {
//空鏈表或只有一個節(jié)點涉馁，直接返回
if (node == null || node.getNext() == null) {
return node;
}
//三個指針贪庙，一個temp先走了兩步，后續(xù)每次一步
//指針一，當前待反轉節(jié)點截碴，起步點為1
Node root=node;
//指針二孔庭，每次緩存當前節(jié)點的下一個節(jié)點尺上，起步點為2
Node preNode=node.getNext();
//指針三，為待反轉節(jié)點待下一個節(jié)點圆到，用來解決反轉后斷鏈問題怎抛，起步點為3
Node temp = node.getNext().getNext();
//當前節(jié)點待下一個節(jié)點，用來緩存待反轉的節(jié)點
if (temp == null) {
//鏈表長度為2芽淡，直接反轉
node.getNext().setNext(node);
root=node.getNext();
node.setNext(null);
} else {
//鏈表長度大于2時
//跳出條件為快指針為null時马绝，此時已經(jīng)循環(huán)到鏈表最后兩位
while (temp!=null) {
//通過指針二實現(xiàn)反轉
preNode.setNext(root);
//當前節(jié)點后移一步
root=preNode;
//指針二后移一步
preNode=temp;
//指針三后移一步
temp=temp.getNext();
}
//最后兩位處理，將最后兩個節(jié)點進行反轉
preNode.setNext(root);
root=preNode;
//把原鏈表首節(jié)點的下一個節(jié)點置為空
node.setNext(null);
}
return root;
}
可以看出兩個方法,遞歸法會出現(xiàn)兩個節(jié)點指向同一節(jié)點情況,三指針法會出現(xiàn)斷鏈情況.比較而言,遞歸法更簡潔.
