目錄
- （一）經典迭代
- （二）用堆疊解決
- （三）雙鏈表求解
- （四）遞回求解
題目：
給你單鏈表的頭節點 head ，請你反轉鏈表，并回傳反轉后的鏈表，
示例 1：
輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]
示例 2：
輸入：head = [1,2]
輸出：[2,1]
示例 3：
輸入：head = []
輸出：[]
（一）經典迭代
用while回圈遍歷串列，將每一個節點的指向改為前一個節點，把最后一個節點當作一個新的頭節點回傳，在遍歷的程序中，由于當前節點的指向改變，我們就無法找到下一個節點，因此我們需要提前儲存下一個節點，
詳細代碼及動態圖：
public class Solution {
public ListNode ReverseList(ListNode head) {
//定義cur節點代表當前需要反轉的節點，cur一開始處于頭節點的位置
ListNode cur=head;
//定義prev為反轉節點的前一個節點，即左邊的節點，初始化為null
ListNode prev=null;
//回圈條件為cur節點走完全部的節點
while(cur!=null){
//定義一個curNext節點，永遠指向cur的下一個節點，防止丟失
ListNode curNext=cur.next;
//反轉關鍵：將當前節點的指向改為前一個節點
cur.next=prev;
//prev向后到cur位置
prev=cur;
//cur向后到下一個需要反轉的節點
cur=curNext;
}
//prev最后所在的位置就是新的頭節點，
return prev;
}
}
（二）用堆疊解決
堆疊的特點是先進后出，
反轉鏈表可以利用這個特點，正向依次放入節點，最后依次彈出節點，
public class Solution {
public ListNode ReverseList(ListNode head) {
Stack<ListNode> stack=new Stack<>();
//遍歷串列，依次放入堆疊中
while(head!=null){
stack.push(head);
head=head.next;
}
//如果是空鏈表，回傳null
if(stack.isEmpty()) return null;
//node節點代表正在存放的節點
ListNode node=stack.pop();
//dummy作為新鏈表的頭節點
ListNode dummy=node;
while(!stack.isEmpty()){
//定義一個tmpNode節點暫時接受下一個彈出的節點
ListNode tmpNode=stack.pop();
//讓node節點指向下一個節點
node.next=tmpNode;
//更新node節點
node=node.next;
}
//置空最后一個節點的next，否則最后一個節點和倒數第二個節點會構成環
node.next=null;
return dummy;
}
}
（三）雙鏈表求解
創建一個新的鏈表，每次把原鏈表的頭節點摘掉，放到新鏈表里當作頭節點，程序如下圖：
詳細代碼及解釋：
public class Solution {
public ListNode ReverseList(ListNode head) {
//新鏈表頭節點
ListNode newHead=null;
while(head!=null){
//定義tmp暫時儲存head的下一個節點
ListNode tmp=head.next;
//將head的指向改為新鏈表的頭節點
//就是將新鏈表掛到掛到head的后面
head.next=newHead;
//更新頭節點
newHead=head;
//此時舊鏈表頭節點的下一個節點成為頭節點
head=tmp;
}
return newHead;
}
}
（四）遞回求解
遞回解法最關鍵的一點是 ：
每次遞回后的回傳都是將后序鏈表反轉并回傳頭節點的參考，
詳細程序如下：
代碼如下：
class Solution {
public ListNode reverseList(ListNode head) {
//遞回的終止條件
if (head == null || head.next == null) {
return head;
}
//新的頭節點
ListNode newHead = reverseList(head.next);
//將當前需要反轉的節點的下一個節點的參考指向自己
head.next.next = head;
//防止成環
head.next = null;
return newHead;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/341883.html
標籤：其他
上一篇：滲透學習總結-Windows基礎