代码随想录刷题第三天|203. 移除链表元素、707设计链表、206、反转链表

203、移除链表元素

• 思路一：利用虚拟头节点，将移除操作一致性
• 代码

dummyHead := new(ListNode)
dummyHead.Next = head
cur := dummyHead
for cur.Next != nil {
    if cur.Next.Val == val {
        cur.Next = cur.Next.Next
    } else {
        cur = cur.Next
    }
}
return dummyHead.Next

• 思路二：一般做法，不利用虚拟头节点
• 代码

for head != nil && head.Val == val {
    head = head.Next
}
cur := head
for cur != nil && cur.Next != nil {
    if cur.Next.Val == val {
        cur.Next = cur.Next.Next
    } else {
        cur = cur.Next
    }
}
return head

707、设计链表

• 代码

// 节点结构体
type Node struct {
    val int
	next *Node
}
// MylinkedList是一个对象，需要去实现LinkedList接口的所有方法
type MyLinkedList struct {
    DummyHead *Node //虚拟头节点
    Size int //链表长度
}

//创建一个链表 
func Constructor() MyLinkedList { //成功
    // 创建一个虚拟头节点，非真正的头节点(真正的头节点是数组第一个节点)
   dummyhead := &Node{
		val: -1,
		next: nil,
	}
	return MyLinkedList{
		DummyHead: dummyhead,
		Size: 0,
	}
}
// 获取index位置的元素Val
func (this *MyLinkedList) Get(index int) int {
	if index < 0 || index > this.Size -1 {
		return -1
	}
	var cur *Node = this.DummyHead.next
	for i := 0; i < index; i++ {
		cur = cur.next
	}
	return cur.val
}

//在头节点之前添加节点
func (this *MyLinkedList) AddAtHead(val int)  {
	//newNode := new(Node)
	//newNode.val = val
	var newNode = &Node{val: val, next: nil}
	newNode.next = this.DummyHead.next
	this.DummyHead.next = newNode
	this.Size++
}

//在尾部插入节点
func (this *MyLinkedList) AddAtTail(val int)  {
	var newNode = &Node{val: val, next: nil}
	cur := this.DummyHead
	for cur.next != nil {
		cur = cur.next
	}
	cur.next = newNode
	this.Size++
}

//在第n个节点前插入
func (this *MyLinkedList) AddAtIndex(index int, val int) {
	if index > this.Size {
		return
	} else if index == this.Size {
		this.AddAtTail(val)
		return
	} else if index < 0 {
		index = 0
	}
	var newNode = &Node{val: val, next: nil}
	cur := this.DummyHead
	//找到符合插入的位置
	for i := 0; i < index; i++ {
		cur = cur.next
	}
	newNode.next = cur.next
	cur.next = newNode
	this.Size++
}

//删除第n个节点
func (this *MyLinkedList) DeleteAtIndex(index int)  {
	if index < 0 || index >= this.Size {
		return
	}
	cur := this.DummyHead
	for i := 0; i < index; i++ {
		cur = cur.next
	}
	cur.next = cur.next.next
	this.Size--
}

206、反转链表

• 代码

func reverseList(head *ListNode) *ListNode {
	cur := head
	var pre  *ListNode//上一个节点
	for cur != nil {
		tmp := cur.Next //保存当前节点的下一个节点
		cur.Next = pre
		pre = cur
		cur = tmp
	}
	return pre
}