代码随想录链表 01

1. 203.移除链表元素

题目链接: LeetCode 203.移除链表元素

思路

使用虚拟头节点规避头节点删除问题

我的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    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
}

2. 707. 设计链表

题目链接: LeetCode 707. 设计链表

解法

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
90
91
92
93
94
95
96
97
98
99
100
101
102
type SingleNode struct {
	Val  int         // 节点的值
	Next *SingleNode // 下一个节点的指针
}

type MyLinkedList struct {
	dummyHead *SingleNode // 虚拟头节点
	Size      int         // 链表大小
}


func Constructor() MyLinkedList {
    newNode := &SingleNode{ // 创建新节点
		-999,
		nil,
	}
	return MyLinkedList{ // 返回链表
		dummyHead: newNode,
		Size:      0,
	}
}


func (this *MyLinkedList) Get(index int) int {
    if this == nil || index < 0 || index >= this.Size {
		return -1
	}
    cur := this.dummyHead.Next   // 设置当前节点为真实头节点
	for i := 0; i < index; i++ { // 遍历到索引所在的节点
		cur = cur.Next
	}
	return cur.Val
}


func (this *MyLinkedList) AddAtHead(val int)  {
    newNode := &SingleNode{Val: val}   // 创建新节点
	newNode.Next = this.dummyHead.Next // 新节点指向当前头节点
	this.dummyHead.Next = newNode      // 新节点变为头节点
	this.Size++                        // 链表大小增加1
}


func (this *MyLinkedList) AddAtTail(val int)  {
    newNode := &SingleNode{Val: val}
    cur := this.dummyHead
    for cur.Next != nil {
        cur = cur.Next
    }
    cur.Next = newNode
    this.Size++
}


func (this *MyLinkedList) AddAtIndex(index int, val int)  {
    if this == nil {
        return
    }

    if index < 0 {
        index = 0
    }
    if index > this.Size {
        return
    }
    prev := this.dummyHead              // 从 dummyHead 开始
    for i := 0; i < index; i++ {        // 走 index 步，落在前驱
        prev = prev.Next
    }

    newNode := &SingleNode{Val: val}
    newNode.Next = prev.Next
    prev.Next = newNode
    this.Size++
}


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
	}
	if cur.Next != nil {
		cur.Next = cur.Next.Next // 当前节点直接指向下下个节点，即删除了下一个节点
	}
	this.Size-- // 注意删除节点后应将链表大小减一
}



/**
 * Your MyLinkedList object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Get(index);
 * obj.AddAtHead(val);
 * obj.AddAtTail(val);
 * obj.AddAtIndex(index,val);
 * obj.DeleteAtIndex(index);
 */

核心思路

3. 206. 反转链表

题目链接: LeetCode 206. 反转链表

思路

使用双指针

我的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    cur := head
    for cur != nil{
        tem := cur.Next
        cur.Next = pre
        pre = cur
        cur = tem
    }
    return pre
}

学习资源

更新日期: 2026-02-20