LeetCode.jpg
目錄鏈接：http://www.itdecent.cn/p/9c0ada9e0ede
反轉(zhuǎn)一個單鏈表
LeetCode 206. 反轉(zhuǎn)鏈表(Reverse Linked List)
示例:
輸入:1->2->3->4->5->NULL輸出:5->4->3->2->1->NULL
切題
一、Clarification
只需注意為空鏈表的情況
二、Possible Solution
1、迭代
2、遞歸
可利用哨兵簡化實現(xiàn)難度
Python3 實現(xiàn)
反轉(zhuǎn)鏈表(Reverse Linked List) Py3 迭代實現(xiàn)
1、迭代實現(xiàn)
# @author:leacoder
# @des: 迭代實現(xiàn) 反轉(zhuǎn)鏈表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head is None:
return None
prev = None # 利用哨兵
cur = head
while cur:
'''
tmp = cur.next
cur.next = prev
prev = cur
cur = tmp
使用python 語法糖 簡化
'''
cur.next, prev, cur = prev, cur ,cur.next
return prev
實現(xiàn)邏輯 與 C++、Java 無差別，但是采用了一種賦值機(jī)制即多元賦值
采用這種方式賦值時，等號兩邊的對象都是元組并且元組的小括號是可選的。通常形式為
x, y = 1,'a string'
等同于(x, y) = (1,'a string')
這種賦值類型最經(jīng)常用到的環(huán)境是變量交換，形如
x, y = y, x
這種交換方式無需中間變量即可交換兩個變量的值
x = 123
y = 'a string'
print(x,y)
x, y = y, x
print(x,y)
輸出結(jié)果：
123 a string
a string 123
遞歸實現(xiàn)
Java實現(xiàn)
Java實現(xiàn)邏輯上與C++無區(qū)別
1、迭代實現(xiàn) Java
反轉(zhuǎn)鏈表(Reverse Linked List) JAVA 迭代實現(xiàn)
2、遞歸實現(xiàn) Java
反轉(zhuǎn)鏈表(Reverse Linked List) JAVA 遞歸實現(xiàn)
C++實現(xiàn)
1、迭代實現(xiàn) C++
反轉(zhuǎn)鏈表(Reverse Linked List)C++迭代實現(xiàn)
/**
* @author:leacoder
* @des: 迭代實現(xiàn) 反轉(zhuǎn)鏈表
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur = head; //當(dāng)前指針節(jié)點
ListNode* prev = NULL; //前指針節(jié)點
ListNode* temp = NULL; //臨時節(jié)點
while(NULL!=cur){
temp = cur->next; //臨時節(jié)點，暫存當(dāng)前節(jié)點的下一節(jié)點(斷開處的節(jié)點)，用于后移
cur->next = prev; //將當(dāng)前節(jié)點指向它前面的節(jié)點
prev = cur; //前指針后移
cur = temp; //當(dāng)前指針后移
}
return prev;
}
};
2、遞歸實現(xiàn) C++
反轉(zhuǎn)鏈表(Reverse Linked List)C++遞歸實現(xiàn)
/**
* @author:leacoder
* @des: 遞歸實現(xiàn) 反轉(zhuǎn)鏈表
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
//第一個條件是判斷遞歸開始，傳入的參數(shù)的合法性。第二個是遞歸的終止條件
if (NULL==head || NULL==head->next)
return head;
ListNode* result = reverseList(head->next); // 循環(huán)遞歸找到最后一個節(jié)點 (head->next為最后一節(jié)點） 那么 result指向最后節(jié)點 以【A B C D】為例 指向 D
head->next->next = head;//以【A B C D】為例 最底部到達(dá)此處時 head 為 C ,head->next 為 D ，反轉(zhuǎn)為 head->next->next 為 C (head)
head->next = NULL; //以【A B C D】為例 斷開 C D 之間連接 C 的 next 指向 NULL，即為 head->next = NULL 如果不斷掉 C D成環(huán) 遞歸無法終止
return result;
}
};
遞歸實現(xiàn)注意傳入的參數(shù)的合法性以及遞歸的終止條件終止條件的判斷，特別注意 最后
head->next = NULL
置空不然鏈表成環(huán)
GitHub鏈接：
https://github.com/lichangke/LeetCode
個人Blog:
https://lichangke.github.io/
歡迎大家來一起交流學(xué)習(xí)
