009.单双链表及其反转-堆栈诠释

前置知识：无

建议：本节内容比较初级，会的同学可以直接跳过

按值传递、按引用传递 §

左神：我不知道为什么如此多的同学会犯这种错误，这完全是语言问题

这不用多说了，是编程中的基础知识

其实都是值传递，只是传递的值代表的是数据本身，还是指向内存空间的某个地址

罗列一下相关的知识：

• 内存空间中的栈空间（函数执行栈）、堆空间
• *：解指针操作符、指针类型；&：取地址操作符
• 基本数据类型、引用（对象）数据类型

单链表、双链表的定义 §

单链表 §

type LinkedNode struct {
	Val  any
	Next *LinkedNode // 指向下一个链表节点
}

双链表 §

type DLinkedNode struct {
	Val  any
	Prev *LinkedNode // 指向上一个链表节点
	Next *LinkedNode // 指向下一个链表节点
}

Go 标准库中的双向链表

反转链表 §

反转单链表 的题之前做了很多遍了

反转双链表思路一样，只是多了一条向前指的指针

堆栈诠释：不理解可以画一下各个指针的变化情况，用人脑模拟一下每次循环各个指针是如何指的

type DLinkedNode struct {
  Val  int
  Prev *DLinkedNode
  Next *DLinkedNode
}
 
func reverse(head *DLinkedNode) *DLinkedNode {
  var (
    cur  = head
    prev *DLinkedNode
    next *DLinkedNode
  )
 
  for cur != nil {
    next = cur.Next
    cur.Next = prev
    cur.Prev = next
    prev = cur
    cur = next
  }
 
  return prev
}

对数器 测试一下：

package main
 
import (
  "fmt"
  "math/rand"
)
 
func main() {
  N := 100
  V := 1000
  testTimes := 50000
 
  ok := true
  for i := 0; i < testTimes; i++ {
    head := generateRandomDLinkedList(N, V)
    // fmt.Println("head")
    // printDLinkedList(head)
    // fmt.Println()
 
    copiedHead := copyDLinkedList(head)
    // fmt.Println("copiedHead")
    // printDLinkedList(copiedHead)
    // fmt.Println()
 
    reverse(copiedHead)
    // reversedHead := reverse(copiedHead)
    // fmt.Println("reversedHead")
    // printDLinkedList(reversedHead)
    // fmt.Println()
 
    curHead := head
    curCopiedHead := copiedHead
    for curHead != nil {
      if curHead.Val != curCopiedHead.Val {
        ok = false
        break
      }
      if curHead.Prev == nil || curCopiedHead.Next == nil {
        if !(curHead.Prev == nil && curCopiedHead.Next == nil) {
          ok = false
          break
        }
      } else if curHead.Prev.Val != curCopiedHead.Next.Val {
        ok = false
        break
      }
      curHead = curHead.Next
      curCopiedHead = curCopiedHead.Prev
    }
  }
  if ok {
    fmt.Println("成功")
  } else {
    fmt.Println("失败")
  }
}
 
func generateRandomDLinkedList(N, V int) *DLinkedNode {
  n := rand.Intn(N + 1)
  if n == 0 {
    return nil
  }
  head := &DLinkedNode{
    Val: rand.Intn(V),
  }
  prev := head
  n--
  for ; n > 0; n-- {
    node := &DLinkedNode{
      Val: rand.Intn(V),
    }
    prev.Next = node
    node.Prev = prev
    prev = node
  }
 
  return head
}
 
  
 
func copyDLinkedList(head *DLinkedNode) *DLinkedNode {
  if head == nil {
    return nil
  }
  newHead := &DLinkedNode{
    Val: head.Val,
  }
  prev := newHead
  head = head.Next
  for head != nil {
    newNode := &DLinkedNode{
      Val: head.Val,
    }
    prev.Next = newNode
    newNode.Prev = prev
    prev = newNode
    head = head.Next
  }
 
  return newHead
}
 
func printDLinkedList(head *DLinkedNode) {
  var prev *DLinkedNode
  fmt.Print("Next: ")
  for head != nil {
    fmt.Printf("%d -> ", head.Val)
    prev = head
    head = head.Next
  }
  fmt.Println("nil")
 
  fmt.Print("Prev: ")
  for prev != nil {
    fmt.Printf("%d -> ", prev.Val)
    prev = prev.Prev
  }
  fmt.Println("nil")
}
 
// ------------------------------------------------------
 
type DLinkedNode struct {
  Val  int
  Prev *DLinkedNode
  Next *DLinkedNode
}
 
func reverse(head *DLinkedNode) *DLinkedNode {
  var (
    cur  = head
    prev *DLinkedNode
    next *DLinkedNode
  )
 
  for cur != nil {
    next = cur.Next
    cur.Next = prev
    cur.Prev = next
    prev = cur
    cur = next
  }
 
  return prev
}

备注 §

链表题目在笔试、面试中的意义就是检验 coding 能力如何

更难的题目会在【必备】课程里讲述