給你單鏈表的頭節(jié)點(diǎn) head ，請(qǐng)你反轉(zhuǎn)鏈表炊汹，并返回反轉(zhuǎn)后的鏈表篡撵。
反轉(zhuǎn)鏈表示例.jpg
進(jìn)階：鏈表可以選用迭代或遞歸方式完成反轉(zhuǎn)。你能否用兩種方法解決這道題坷澡？
摘一個(gè)示例做個(gè)說(shuō)明.
示例 1：
輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]
條件分析:
- 單鏈表頭節(jié)點(diǎn) -> 需要從頭節(jié)點(diǎn)開(kāi)始反轉(zhuǎn)
解決思路1:
- 根據(jù)分析1,采用迭代方式進(jìn)行反轉(zhuǎn)
先定義返回的空鏈表和循環(huán)鏈表(需要反轉(zhuǎn)的鏈表).然后當(dāng)循環(huán)鏈表不空的時(shí)候進(jìn)行循環(huán)(即鏈表沒(méi)有到尾節(jié)點(diǎn)),定義臨時(shí)變量為循環(huán)鏈表的next,然后讓循環(huán)鏈表的next指向返回鏈表.返回的鏈表為循環(huán)鏈表.然后循環(huán)鏈表為臨時(shí)鏈表(即下一個(gè)節(jié)點(diǎn)后的鏈表)
func reverseList(_ head: ListNode?) -> ListNode? {
// 返回鏈表
var newHead: ListNode? = nil
// 循環(huán)節(jié)點(diǎn)
var old = head
while old != nil {
// 先定義臨時(shí)變量存儲(chǔ)next
let tmp = old?.next
// 節(jié)點(diǎn)指向返回鏈表(定義新鏈表承接)
old?.next = newHead
// 返回鏈表等于循環(huán)鏈表
newHead = old
// 讓循環(huán)鏈表為臨時(shí)變量,進(jìn)行繼續(xù)循環(huán)
old = tmp
}
return newHead
}
解決思路2:
- 根據(jù)分析1,采用遞歸方式進(jìn)行反轉(zhuǎn)
先判斷鏈表是否為空或者單節(jié)點(diǎn)鏈表,是則直接返回(也用以結(jié)束遞歸).然后開(kāi)始遞歸節(jié)點(diǎn),直到尾節(jié)點(diǎn)結(jié)束遞歸.然后從尾部開(kāi)始反轉(zhuǎn)鏈表節(jié)點(diǎn).直到頭節(jié)點(diǎn).然后置空頭節(jié)點(diǎn)的next即可.
func reverseList(_ head: ListNode?) -> ListNode? {
// 單鏈表和空鏈表直接返回
if head == nil || head?.next == nil{
return head
}
// 遞歸調(diào)用,直到尾節(jié)點(diǎn)
let node : ListNode? = reverseList(head?.next)
// 直接反轉(zhuǎn)鏈表節(jié)點(diǎn)指向
head?.next?.next = head
// 最后next置空
head?.next = nil
return node
}
測(cè)試用例:
let endNode = ListNode.init(0)
let fourNode = ListNode.init(1)
fourNode.next = endNode
let threeNode = ListNode.init(2)
threeNode.next = fourNode
let secondNode = ListNode.init(3)
secondNode.next = threeNode
let firstNode = ListNode.init(4)
firstNode.next = secondNode
let headNode = ListNode.init(5)
headNode.next = firstNode
考察要點(diǎn):
- 遞歸
- 鏈表
