代码随想录算法训练营第3天 | leetcode203、leetcode707、leetcode206

（本合集全部为Go语言实现）

相关文章链接：203题解 707题解 206题解
相关视频链接：

Leetcode203

状态：秒了
实现过程中的难点：链表遍历一定要记得指针后移。另外，在头指针前加入一个新的临时头节点可以统一整个遍历过程，否则需要先确定初始时两指针的状态

个人写法

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
  tmpHead := &ListNode{-1, head}
  pre, post := tmpHead, head
  for post != nil {
    if post.Val == val {
      pre.Next = post.Next
      post = pre.Next
    } else {
      pre = pre.Next
      post = pre.Next
    }
  }
  return tmpHead.Next
}

Leetcode707

状态：稍微有点耗时间
实现过程中的难点：注意节点增删时指针指向变化的正确性

个人写法

type MyLinkedList struct {
  Size int
  Head *Node
}

type Node struct {
    Val int
    Next *Node
}

func Constructor() MyLinkedList {
  return MyLinkedList{0, &Node{-1, nil}}
}

func (this *MyLinkedList) Get(index int) int {
  if index >= this.Size {
    return -1
  }
  ptr := this.Head
  for i := 0; i < index; i++ {
      ptr = ptr.Next
  }
  return ptr.Next.Val
}

func (this *MyLinkedList) AddAtHead(val int)  {
  newNode := &Node{val, this.Head.Next}
  this.Head.Next = newNode
  this.Size++
}

func (this *MyLinkedList) AddAtTail(val int)  {
  ptr := this.Head
  for ptr.Next != nil {
    ptr = ptr.Next
  }
  ptr.Next = &Node{val, nil}
  this.Size++
}


func (this *MyLinkedList) AddAtIndex(index int, val int)  {
  if index > this.Size {
      return
  }
  ptr := this.Head
  for i := 0; i < index; i++ {
      ptr = ptr.Next
  }
  newNode := &Node{val, ptr.Next}
  ptr.Next = newNode
  this.Size++
}


func (this *MyLinkedList) DeleteAtIndex(index int)  {
  if index >= this.Size {
      return
  }
  ptr := this.Head
  for i := 0; i < index; i++ {
      ptr = ptr.Next
  }
  ptr.Next = ptr.Next.Next
  this.Size--
}

Leetcode206

状态：基本秒了
实现过程中的难点：需要明确节点的可访问性，如果需要用到的节点将访问不到，那么就利用临时指针变量保存

个人写法

func reverseList(head *ListNode) *ListNode {
  tmpHead := &ListNode{-1, head}
  var newHead *ListNode = nil
  for tmpHead.Next != nil {
    tmp := tmpHead.Next
    tmpHead.Next = tmpHead.Next.Next
    tmp.Next = newHead
    newHead = tmp
  }
  return newHead
}

今日收获

• 熟悉了链表问题在处理类似遍历的问题时指针变化的方式，以后会更加注意

学习时长：2小时左右