go實現反轉鏈表

反轉鏈表首先討論特殊節點

如果節點在首位,則反轉之後,首位節點的next值為nil。

func reverse(head *ListNode) *ListNode {
 bnode := head//設置默認遍歷的前節點,為head
 temp := head.Next//從head.next節點開始遍歷鏈表
 flage := 0//設置一個標記,用於判斷是否為第一個節點
 var lnext *ListNode//用於臨時保存下一個節點
 for temp != nil {//遍歷當
  lnext = temp.Next//先將遍歷節點的下一個節點進行保存
  temp.Next = bnode//節點反轉,將此節點的next值進行更改,更改為上一個節點
  if flage == 0 {//如果是第一個節點,則flage為0
   bnode.Next = nil//第一個節點翻轉後的next值為nil
   flage = 1//將flage值進行更改,避免之後的節點的next值被更改為nil
  } 
  bnode = temp//將節點進行更新,前節點更改為遍歷節點
  temp = lnext//節點進行更新,由於之前temp.next值已經被更改,但是temp.next值被保存在變量中所以temp = lnext
 }
 return bnode//返回bnode節點,不能返回temp節點,temp為空,因為temp為空是跳出for循環的標志
}

補充:golang 鏈表逆序反轉輸出

鏈表逆序輸出案例代碼

//如何實現鏈表的逆序
package main
import "fmt"
type studentNode struct {
	no   int
	name string
	age  int
	next *studentNode
	pre  *studentNode
}
func reversePrint(head *studentNode) {
	//1.創建一個輔助結點
	temp := head
	//2.判斷這是不是一個空鏈表
	if temp.next == nil { //說明是一個空鏈表
		return
	}
	//3.讓temp指向這個雙向鏈表的最後結點
	for {
		if temp.next == nil {
			break
		}
		temp = temp.next
	} //循環結束則已經指向雙向鏈表的最後結點
//4.遍歷這個鏈表
for{
	fmt.Printf("%d,%s,%d==>",temp.no,temp.name,temp.age)
	temp=temp.pre//依次向前
	if temp.pre==nil{//判斷是不是到瞭鏈表頭
		break
	}
}
}
func insertStudentNode(head *studentNode, newStudentNode *studentNode) {
	//思路:
	//1.先找到該鏈表的最後這個結點
	//2.創建一個輔助結點
	temp := head
	for {
		if temp.next == nil { //表示找到最後
			break
		}
		temp = temp.next //讓temp不斷的指向下一個結點
	}
	//3.將newStudentNode加入到鏈表的最後
	temp.next = newStudentNode
	newStudentNode.pre=temp
}
//正序打印這個雙向鏈表
func originalList(head *studentNode) {
//1.創建一個輔助結點
temp:=head
//2.先判斷這個鏈表是否是空鏈表
if temp.next==nil{
	fmt.Println("這是一個空鏈表")
	return
}
//3.遍歷這個鏈表
for{
	fmt.Printf("%d,%s,%d==>",temp.next.no,temp.next.name,temp.next.age)
	temp=temp.next
if temp.next == nil{
	break
}
}
}
//創建一個雙向鏈表
func createlink()*studentNode {
	//1.先創建一個頭結點
	head := &studentNode{}
	//2.創建一個新的studentNode
	stuLisa := &studentNode{
		no:   1,
		name: "Lisa",
		age:  24,
	}
	stuBob := &studentNode{
		no:   2,
		name: "Bob",
		age:  25,
	}	
	stuNick := &studentNode{
			no:   3,
			name: "Nick",
			age:  27,
		}
		stuMark := &studentNode{
			no:   4,
			name: "Mark",
			age:  29,
		}
		//3.加入結點
		insertStudentNode(head, stuLisa)
		insertStudentNode(head, stuBob)
		insertStudentNode(head, stuNick)
		insertStudentNode(head, stuMark)
		return head
}
//逆序打印這個雙向鏈表
func main() {
	head :=createlink()
	fmt.Println("正序打印")
	originalList(head)
	fmt.Println()
	fmt.Println("逆序打印")
	reversePrint(head)
}

結果

在這裡插入圖片描述

以上為個人經驗,希望能給大傢一個參考,也希望大傢多多支持WalkonNet。如有錯誤或未考慮完全的地方,望不吝賜教。

推薦閱讀: