part1

203.移除链表元素

分析

1. 不设置虚拟头结点，需要处理头结点相等的情况
2. 设置虚拟头结点，需要注意最后返回的头结点是虚拟头结点的下一个结点
3. 设置当前移动结点cur，当cur.Next.Val == val时，移除链表元素cur.Next直接连cur.Next.Next，其他情况cur向后移
4. 出循环条件cur.Next == nil

代码

// 单链表结点
type ListNode struct {
	Val  int
	Next *ListNode
}

func removeElements1(head *ListNode, val int) *ListNode {
	// 处理头节点
	for head != nil && head.Val == val {
		head = head.Next
	}

	// 如果链表为空或已经处理完毕
	if head == nil {
		return nil
	}

	cur := head

	// 处理其余节点
	for cur != nil && cur.Next != nil {
		if cur.Next.Val == val {
			cur.Next = cur.Next.Next
		} else {
			cur = cur.Next
		}
	}
	return head // 返回头节点，而不是当前节点
}

// 设置虚拟头结点
func removeElements2(head *ListNode, val int) *ListNode {
	dum := &ListNode{}

	dum.Next = head

	cur := dum

	for cur.Next != nil {
		if cur.Next.Val == val {
			cur.Next = cur.Next.Next
		} else {
			cur = cur.Next
		}
	}

	return dum.Next
}

707.设计链表

分析

对我来说有点难度～

代码

// MyLinkedList 单链表结构
type MyLinkedList struct {
	Head *ListNode // 头节点
	Size int       // 链表大小
}

func Constructor() MyLinkedList {
	return MyLinkedList{
		Head: nil,
		Size: 0,
	}
}

func (l *MyLinkedList) Get(index int) int {
	if index < 0 || index >= l.Size {
		return -1
	}

	cur := l.Head
	for i := 0; i < index; i++ {
		cur = cur.Next
	}

	return cur.Val
}

func (l *MyLinkedList) AddAtHead(val int) {
	newNode := &ListNode{
		Val:  val,
		Next: l.Head,
	}

	l.Head = newNode
	l.Size++
}

func (l *MyLinkedList) AddAtTail(val int) {
	newNode := &ListNode{Val: val, Next: nil}

	if l.Head == nil {
		l.Head = newNode
	} else {
		cur := l.Head
		for cur.Next != nil {
			cur = cur.Next
		}

		cur.Next = newNode
	}

	l.Size++
}

func (l *MyLinkedList) AddAtIndex(index int, val int) {
	if index > l.Size {
		return
	}

	if index <= 0 {
		l.AddAtHead(val)
		return
	}

	if index == l.Size {
		l.AddAtTail(val)
		return
	}

	cur := l.Head
	for i := 0; i < index-1; i++ {
		cur = cur.Next
	}

	newNode := &ListNode{Val: val, Next: cur.Next}
	cur.Next = newNode
	l.Size++
}

func (l *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 || index >= l.Size {
		return
	}

	if l.Head == nil {
		return
	}

	if index == 0 {
		l.Head = l.Head.Next
	} else {
		cur := l.Head
		for i := 0; i < index-1; i++ {
			cur = cur.Next
		}
		if cur.Next != nil {
			cur.Next = cur.Next.Next
		}
	}

	l.Size--
}

206.反转链表

分析

1. 双指针，前一个指针prev和当前指针cur
2. 保存cur.Next，然后将cur.Next指向prev
3. 移动prev和cur指针
4. 最后返回prev（新的头节点）

解题，想象一下反转的步骤然后按顺序填写代码，最后遍历到cur == nil时出循环

代码

func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	var prev *ListNode
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = prev
		prev = cur
		cur = next
	}
	return prev
}

总结

1. 单链表
2. 虚拟头结点
3. 双指针