iT邦幫忙

2021 iThome 鐵人賽

DAY 8
0
Software Development

算法30天系列 第 8

Day.8 Reverse Linked List

Leetcode #206. Reverse Linked List

簡單來說這一題要做反轉鏈結
ex.
input: 1->2->3->4
output: 4->3->2->1

如果你沒做過這題,強烈建議你先思考一下怎麼解。


防雷
防雷
防雷


最直覺的方式可以新建一個slice([]*ListNode),去把全部的節點都放進去,最後slice從尾去讀取,重新建一個鏈結就行了。

這樣做的時間複雜度為O(n),空間複雜性O(n)要用slice存下鏈結的地址。

現在為大家介紹一個更好的解法,可以省下一些記憶體。

先來看一下它的流程:

1 2 3 4
2 1 3 4
3 2 1 4
4 3 2 1

每一次新節點都把第一個節點接在後面,當你跑完本個鏈結,就完成反轉了。

來看一下程式:

func reverseLinkedList(head *ListNode) *ListNode {
	// prevNode一開始為是空
	// 這樣第一個節點的next會接到nil,才不會造成無限的鏈結
	var prevNode *ListNode
	currentNode := head

	// 節點交換的過程
	for currentNode != nil {
		temp := currentNode.Next
		currentNode.Next = prevNode // 最前面的節點接到目前節點的後面
		prevNode = currentNode
		currentNode = temp
	}

	return prevNode // 回傳第一個節點
}

明天來解其他題目~


上一篇
Day.7 鏈結
下一篇
Day.9 Add Two Numbers
系列文
算法30天30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言