題目
206.反轉鏈表
反轉一個單鏈表。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
進階:
你可以迭代或遞歸地反轉鏈表。你能否用兩種方法解決這道題？
思路
上來還是用能想到最簡單的方法。
先遍歷鏈表，然后把鏈表的元素緩存起來，然后倒著遍歷數組，重新創(chuàng)建一個新的鏈表
代碼如下:
func reverseList(_ head: ListNode?) -> ListNode? {
var array = [Int]()
var ln = head
while ln != nil {
array.append(ln!.val)
ln = ln?.next
}
let rln = ListNode(0)
ln = rln
while array.count > 0 {
let num = array.last!
ln?.next = ListNode(num)
ln = ln?.next
array.removeLast()
}
return rln.next
}
運行結果居然是通過了，O(n2)的時間復雜度，用時24ms，戰(zhàn)勝69.34% Swift 提交?？赡苁且驗橛美龜盗刻?，并且數據量也不大的原因。下面當然是要繼續(xù)優(yōu)化代碼，看看能不能降低時間復雜度。
首先還是要遍歷鏈表，每次取出鏈表第一個元素，然后把之前創(chuàng)建的鏈表賦值給賦值給當前元素的 next ，然后再更新需要遍歷的數據，就可以了，詳細的可以看代碼注釋，就比較清楚了。
代碼如下:
class Solution {
func reverseList(_ head: ListNode?) -> ListNode? {
var rln: ListNode?
var ln = head
while ln != nil {
//ln = 12345 2345 345 ...
//先取出以后需要遍歷的數據
//next = 2345 345 45 ...
let next = ln!.next
//將之前創(chuàng)建的鏈表賦值給當前值的next
//ln = 1 21 321 ...
ln!.next = rln
//1 21 321 ...
//更新新的遍歷數據
rln = ln!
//2345 345 45 ...
ln = next
}
return rln
}
}
這次的時間復雜度為 O(n) ，耗時 16ms ，戰(zhàn)勝了 99.27% 的 Swift 提交。
下面繼續(xù)題目進階說的，使用遞歸來做這道題。
遞歸的話，首先就要不斷遞歸獲取到最后的值，然后再返回值時處理數據，讓返回的鏈表的 next 為當前 head 的值即可。注意的是需要 head!.next = nil 切斷引用循環(huán)。
func reverseList(_ head: ListNode?) -> ListNode? {
guard let next = head?.next else {
return head
}
let ln = reverseList(next)
//因為class引用所以直接操作next即可
next.next = head
//切斷引用循環(huán)
head!.next = nil
return ln
}
遞歸的時間復雜度也是 O(n) ，實際比循環(huán)還快，耗時 12ms ，戰(zhàn)勝了 100% 的 Swift 提交。估計也是因為用例比較少，正常的時間波動。
