代码随想录算法训练营第三天| 203.移除链表元素、707.设计链表、206.反转链表。

代码随想录算法训练营第三天| 203.移除链表元素、707.设计链表、206.反转链表。

203. 移除链表元素

题目链接：leetcode题目链接

文章讲解：代码随想录(programmercarl.com)

视频讲解：链表基础操作| LeetCode：203.移除链表元素

状态：AC

思路

删除元素还是比较简单的，假设q = p.Next，如果删除q则是p.Next = p.Next.Next，考虑下p.Next.Next是否存在即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
func removeElements(head *ListNode, val int) *ListNode {
	newHead := new(ListNode)
	newHead.Next = head
	p := newHead
	for p.Next != nil {
		if p.Next.Val == val {
			p.Next = p.Next.Next
		} else {
			p = p.Next
		}
	}
	return newHead.Next
}

707. 设计链表

题目链接：leetcode题目链接

文章讲解：代码随想录(programmercarl.com)

视频讲解：帮你把链表操作学个通透！LeetCode：707.设计链表

状态：半AC（AC了但是也没完全AC）

思路

  • (this *MyLinkedList)get(index int) int: 先判断index是否合法，所以需要引入一个新的成员对象size在MyLinkedList中
  • (this *MyLinkedList)AddAtHead(val int): 头插法只需要在新的头之后接入一个新的节点，然后size++
  • (this *MyLinkedList)AddAtTail(val int): 尾插法只需要在整个链表之后接入一个新的节点，然后size++
  • (this *MyLinkedList)DeleteAtIndex(index int): 删除一个元素类似上一题，只不过要判断index是否合法
  • (this *MyLinkedList)AddAtIndex(index int, val): 先判断index是否合法，找到正确位置进行插入

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

type LinkList struct {
	Val  int
	Next *LinkList
}

type MyLinkedList struct {
	size    int
	newHead *LinkList
}

func Constructor() MyLinkedList {
	//return MyLinkedList{}
	node := &LinkList{
		Val:  0,
		Next: nil,
	}
	return MyLinkedList{
		newHead: node,
		size:    0,
	}
}

func (this *MyLinkedList) Get(index int) int {
	if index < 0 || index >= this.size || this == nil {
		return -1
	}
	p := this.newHead.Next
	for i := 0; i < index; i++ {
		p = p.Next
	}
	return p.Val
}

func (this *MyLinkedList) AddAtHead(val int) {
	newNode := &LinkList{
		Val:  val,
		Next: this.newHead.Next,
	}
	this.newHead.Next = newNode
	this.size++
}

func (this *MyLinkedList) AddAtTail(val int) {
	newNode := &LinkList{
		Val:  val,
		Next: nil,
	}
	p := this.newHead
	for p.Next != nil {
		p = p.Next
	}
	p.Next = newNode
	this.size++
}

func (this *MyLinkedList) AddAtIndex(index int, val int) {
	if index < 0 {
		index = 0
	} else if index > this.size {
		return
	}
	newNode := &LinkList{
		Val:  val,
		Next: nil,
	}
	p := this.newHead
	for i := 0; i < index; i++ {
		p = p.Next
	}
	newNode.Next = p.Next
	p.Next = newNode
	this.size++
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 || index >= this.size {
		return
	}
	p := this.newHead
	for i := 0; i < index; i++ {
		p = p.Next
	}
	if p.Next != nil {
		p.Next = p.Next.Next
	}
	this.size--
}

206. 反转链表

题目链接：leetcode题目链接

文章讲解：代码随想录(programmercarl.com)

视频讲解：帮你拿下反转链表 | LeetCode：206.反转链表

状态：AC

思路

  1. 建立新的头结点newHead ，使其newHead.Next = head。
  2. 定义指针p = head.Next(先判断head是否为单节点)，然后手动断链，head.Next = nil
  3. 指针p不断向后，每遍历到一个元素，将这个元素保存到新的节点newNode，并且不断头插到newHead

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func addAtHead(head *ListNode, val int) *ListNode {
	newHead := &ListNode{
		Val:  0,
		Next: head,
	}
	newNode := &ListNode{
		Val:  val,
		Next: newHead.Next,
	}
	newHead.Next = newNode
	return newHead.Next
}

func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	p := head.Next
	head.Next = nil
	for p != nil {
		head = addAtHead(head, p.Val)
		p = p.Next
	}
	return head
}

小结

  • leetcode上的链表的题都是无头链表，所谓的 head 被叫做 虚拟头。我感觉还是叫做无头链表好一些，新建一个头先链接无头链表

  • 以前写过的都是有头链表，换到了无头链表刚开始有点不知所措、插入时候感觉怪怪的，其实都一样

  • Go的new相关或者初始化成员变量有了新的理解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    type SSS struct {
        Val int
    }

    //初始化的方式1
    a := new SSS(1)
    a.Val = 1

    //初始化的方式2
    a := &SSS{
        Val: 1
    }

  • Go的构造函数看起来还有点懵

  • 最近事情太多了，周六上午招聘会、下午学校组织的求职训练营、晚上继续leetcode；周日上午训练营结课、下午再重写下链表、搞搞课题；周一还有个小活动。加油！