Golang 實作【連結清單反轉】

題目

Golang 實作【連結清單反轉】 如何反轉一個單連結清單。

題目示例

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL           

連結清單結構

type ListNode struct {
	Val int
	Next *ListNode
}

           

第一種實作

解題思路：

    利用指針互動的思路

複雜度分析：

時間複雜度 O(N) ： 周遊連結清單使用線性大小時間。

空間複雜度 O(1)： 變量 pre 和 cur 使用常數大小額外空間。

func reverseList(cur *ListNode) *ListNode {
	if cur == nil {
		return nil
	}
	var pre *ListNode
	for cur!=nil {
		//擷取下個節點temp
		temp:=cur.Next
		//因要翻轉，故cur.next=pre 下一個節點等于前一個節點
		cur.Next=pre
		//将目前節點指派給前節點
		pre=cur
		//将temp節點指派給目前節點，用于繼續往下執行
		cur=temp
		//平行指派文法  可讀性差
		//cur.Next,pre,cur=pre,cur,cur.Next
	}
	return pre
}           

第二種實作

    利用遞歸思路實作

func reverseListV2(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	//初始時，pre為nil
	return recur(head,nil)
}

func recur(cur,pre *ListNode) *ListNode  {
	//目前cur為nil 說明到了尾節點
	if cur == nil {
		return pre
	}
	//遞歸反轉，故下個節點，即目前節點，目前節點為前節點
	res:=recur(cur.Next,cur)
	//将前節點，指派給cur.Next
	cur.Next=pre
	return res
}           

Golang解題代碼

type ListNode struct {
	Val int
	Next *ListNode
}


func TestListNode(t *testing.T){
	head := new(ListNode)
	head.Val = 1
	ln2 := new(ListNode)
	ln2.Val = 2
	ln3 := new(ListNode)
	ln3.Val = 3
	ln4 := new(ListNode)
	ln4.Val = 4
	ln5 := new(ListNode)
	ln5.Val = 5
	head.Next = ln2
	ln2.Next = ln3
	ln3.Next = ln4
	ln4.Next=ln5
	//Println(reverseList(head))
	Println(reverseListV2(head))
}

func Println(list *ListNode)  {
	for list!=nil{
		fmt.Printf("val:%v ",list.Val)
		list = list.Next
	}
}
func reverseList(cur *ListNode) *ListNode {
	if cur == nil {
		return nil
	}
	var pre *ListNode
	for cur!=nil {
		//擷取下個節點temp
		temp:=cur.Next
		//因要翻轉，故cur.next=pre 下一個節點等于前一個節點
		cur.Next=pre
		//将目前節點指派給前節點
		pre=cur
		//将temp節點指派給目前節點，用于繼續往下執行
		cur=temp



		//平行指派文法  可讀性差
		//cur.Next,pre,cur=pre,cur,cur.Next
	}
	return pre
}

func reverseListV2(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	//初始時，pre為nil
	return recur(head,nil)
}

func recur(cur,pre *ListNode) *ListNode  {
	//目前cur為nil 說明到了尾節點
	if cur == nil {
		return pre
	}
	//遞歸反轉，故下個節點，即目前節點，目前節點為前節點
	res:=recur(cur.Next,cur)
	//将前節點，指派給cur.Next
	cur.Next=pre
	return res
}

           

結果驗證