反轉(zhuǎn)鏈表
題目：描述
給定一個單鏈表的頭結(jié)點head，長度為n构订，反轉(zhuǎn)該鏈表后，返回新鏈表的表頭悼瘾。
反轉(zhuǎn)鏈表.png
以上轉(zhuǎn)換過程如下圖所示：
示例1
輸入：
{1,2,3}
返回值：
{3,2,1}
示例2
輸入：
{}
返回值：
{}
復(fù)制
說明：
空鏈表則輸出空
1.迭代法
因為單鏈表只能由當(dāng)前節(jié)點查找到后一個節(jié)點审胸，因此使用迭代法時，需要保存當(dāng)前節(jié)點的后一個節(jié)點砂沛。
- curr 指向鏈表的當(dāng)前節(jié)點，next 保存curr節(jié)點的下一個節(jié)點（因為是單鏈表碍庵，不保存的話圆到，改變方向之后就找不到舊節(jié)點的下個節(jié)點了），prev剛開始值為空芽淡，保存當(dāng)前節(jié)點的前一個節(jié)點。
反轉(zhuǎn)列表-迭代法.drawio.png
- 假如單鏈表為[1,2,3,4,5],curr指向第一個節(jié)點1挣菲，核心代碼如下：
next = curr.next //先保存next節(jié)點掷邦，防止節(jié)點斷后，找不到下一個節(jié)點
curr.next = prev
prev = curr, curr = next
Java代碼實現(xiàn)：
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
// 如何調(diào)整鏈表指針抚岗，達(dá)到鏈表反轉(zhuǎn)的目的。
ListNode prev = null; // prev : 指向反轉(zhuǎn)好節(jié)點的最后一個節(jié)點
ListNode curr = head; //指向反轉(zhuǎn)鏈表的第一個節(jié)點
while(curr != null){
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
Python代碼如下：
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev = None
curr = head
while curr is not None:
next = curr.next
curr.next = prev
prev, curr = curr, next
return prev # 注意：此時prev節(jié)點指向最后一個節(jié)點
2.使用“椥担”
由于棧的特點：先入后出，假如要反轉(zhuǎn)的鏈表為[1, 2, 3, 4, 5]胚委，我們把每個節(jié)點壓入到棧中，然后再取出就可以得到反轉(zhuǎn)后的節(jié)點[5, 4, 3, 2, 1]亩冬。具體步驟如下：
棧-反轉(zhuǎn)鏈表.drawio.png
- 遍歷鏈表，把每個節(jié)點依次壓入棧中覆享。
- 再遍歷取出，就實現(xiàn)了鏈表的反轉(zhuǎn)
代碼如下：
java實現(xiàn)：
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
import java.util.Stack;
public class Solution {
public ListNode ReverseList(ListNode head) {
Stack<ListNode> stack = new Stack<>(); // 棧
// 1.把鏈表中的節(jié)點入棧
while(head != null){
stack.push(head);
head = head.next;
}
// 2.判斷棧為空撒顿，則返回null
if(stack.isEmpty())
return null;
// 3.從棧中取出元素连茧，然后組成鏈表核蘸，則為反轉(zhuǎn)后的鏈表
ListNode dummy = stack.pop();
ListNode temp = dummy;
while(!stack.isEmpty()){
temp.next = stack.pop();
temp = temp.next;
}
// 4.最后一個節(jié)點的next要置為空啸驯，否則會構(gòu)成環(huán)
temp.next = null;
return dummy;
}
}
Python代碼：
def ReverseList(self , head: ListNode) -> ListNode:
# write code here
stack = [] #使用列表即可實現(xiàn)棧
while head is not None:
stack.append(head)
head = head.next
if len(stack) == 0:
return None
dummy = stack.pop() # 啞結(jié)點
temp = dummy
while len(stack) != 0:
temp.next = stack.pop()
temp = temp.next
# 最后一個節(jié)點是反轉(zhuǎn)前的頭結(jié)點，一定要讓他的next等于空罚斗，否則會構(gòu)成環(huán)
temp.next = None
return dummy
3.新建鏈表法
如圖所示：遍歷單鏈表中的每一個節(jié)點，一個一個進(jìn)行鏈接，如下圖所示：
新建鏈表.drawio.png
Python代碼如下：
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# 雙鏈表法：
dummy = None # 定義空節(jié)點
while head is not None:
next = head.next # 因為是單鏈表厌衙，先保存下一個節(jié)點
head.next = dummy # 第一個節(jié)點連接到 dummy
dummy, head = head, next # dummy 指向最新的節(jié)點绞绒，head指向下一個節(jié)點婶希，進(jìn)行遍歷
return dummy # 結(jié)束后 dummy 將指向新節(jié)點的頭結(jié)點
java代碼：
class Solution {
public ListNode reverseList(ListNode head) {
// 1.定義啞結(jié)點 dummy
ListNode dummy = null;
while(head != null){
// 2.先保存下一個節(jié)點
ListNode next = head.next;
// 3.原鏈表中的第一個節(jié)點指向dummy
head.next = dummy;
// 4.dummy 指向 head蓬衡，head指向下一個節(jié)點
dummy = head;
head = next;
}
return dummy;
}
}
4.遞歸法
反轉(zhuǎn)鏈表.drawio.png
如圖所示
思路：
- 開始head指向第一個節(jié)點
- 遞歸到倒數(shù)第二個節(jié)點
- 然后改變節(jié)點的方向
- 找到遞歸的出口，反方向回來
def reverse_list(self, head):
if head is None or head.next is None: # 遞歸結(jié)束條件
return head
else:
ans = self.reverse_list(head.next) # 遞歸下一個結(jié)點 到 倒數(shù)第二個結(jié)點
head.next.next = head # 最后一個結(jié)點指向倒數(shù)第二個結(jié)點
head.next = None # 最后一結(jié)點的指針域賦值為空
return ans
