删除单链表中值等于XXX的所有元素
不经意间看到了一个不同寻常的实现方法，觉得挺有意思，于是自己实现了一下，代码真的是简单明了跑得还贼快！
好，现在先在脑海中想想，你会怎么实现？这么简单，5秒钟后，你想到了解决方案，于是你决定验证你的思路，请继续往下看
定义链表节点结构如下：
type ListNode struct {
Next *ListNode
Value int
}
1：最常见思路
定义一个保存上个节点的变量prev，当发现当前节点cur的值等于目标值，就将prev.next = cur.next，一直循环下去，跳过节点值等于目标值的所有节点，即删除了所有值等XXX的节点，golang代码实现如下：
func RemoveNodeNormal(head *ListNode, value int) *ListNode {
var prev *ListNode
for cur := head; cur != nil; cur = cur.Next {
if cur.Value == value {
if prev != nil {
prev.Next = cur.Next
} else {
head = cur.Next
}
} else {
prev = cur
}
}
return head
}
这么简单，我就不做任何说明了，后面会附上完整代码和简单的单测
你的思路是这样的吗？
if 是 || ！不是 {
请继续往下看
}
2：第二常见思路
我要走不寻常路，定义prev变量是不可能的，这次是不可能的，如果发现当前节点值等于目标值，就用下一个节点的值覆盖当前节点的值，当前节点的下一个节点指向下下个节点。代码实现如下：
func RemoveNodeReplace(head *ListNode, value int) *ListNode {
cur := head
for cur != nil && cur.Value == value {
if cur.Next == nil {
return nil
}
cur.Value = cur.Next.Value
cur.Next = cur.Next.Next
}
for cur != nil {
if cur.Next != nil && cur.Next.Value == value {
cur.Next = cur.Next.Next
} else {
cur = cur.Next
}
}
return head
}
3：linus喜欢的代码
linus说代码应该这样写，我就不做任何说明了，你品，你细品！！
func RemoveNode(head *ListNode, value int) *ListNode {
for cur := &head; *cur != nil; {
if (*cur).Value == value {
*cur = (*cur).Next
} else {
cur = &(*cur).Next
}
}
return head
}
完整代码如下，你可以跑着试一下：
package main
import (
"fmt"
)
type ListNode struct {
Next *ListNode
Value int
}
func RemoveNodeNormal(head *ListNode, value int) *ListNode {
var prev *ListNode
for cur := head; cur != nil; cur = cur.Next {
if cur.Value == value {
if prev != nil {
prev.Next = cur.Next
} else {
head = cur.Next
}
} else {
prev = cur
}
}
return head
}
func RemoveNodeReplace(head *ListNode, value int) *ListNode {
cur := head
for cur != nil && cur.Value == value {
if cur.Next == nil {
return nil
}
cur.Value = cur.Next.Value
cur.Next = cur.Next.Next
}
for cur != nil {
if cur.Next != nil && cur.Next.Value == value {
cur.Next = cur.Next.Next
} else {
cur = cur.Next
}
}
return head
}
func RemoveNode(head *ListNode, value int) *ListNode {
for cur := &head; *cur != nil; {
if (*cur).Value == value {
*cur = (*cur).Next
} else {
cur = &(*cur).Next
}
}
return head
}
func ArrayToLink(nums []int) *ListNode {
if len(nums) == 0 {
return nil
}
head := &ListNode{
Value: nums[0],
}
tail := head
for i := 1; i < len(nums); i++ {
tail.Next = &ListNode{
Value: nums[i],
}
tail = tail.Next
}
return head
}
func LinkToArray(head *ListNode) []int {
var array []int
for ; head != nil; head = head.Next {
array = append(array, head.Value)
}
return array
}
func ArrayEqual(nums1, nums2 []int) bool {
if len(nums1) != len(nums2) {
return false
}
for i := 0; i < len(nums1); i++ {
if nums1[i] != nums2[i] {
return false
}
}
return true
}
func main() {
tests := []struct {
nums []int
value int
res []int
}{
{
[]int{},
1,
[]int{},
},
{
[]int{1},
1,
[]int{},
},
{
[]int{1, 2},
1,
[]int{2},
},
{
[]int{1, 2},
2,
[]int{1},
},
{
[]int{1, 2, 1, 3, 1, 4, 1, 1, 1, 1, 1},
1,
[]int{2, 3, 4},
},
{
[]int{1, 2, 3, 2, 4, 2},
2,
[]int{1, 3, 4},
},
{
[]int{3, 1, 3, 2, 3, 4, 3},
3,
[]int{1, 2, 4},
},
{
[]int{4, 1, 4, 2, 4, 3, 4, 4, 4, 4, 4},
4,
[]int{1, 2, 3},
},
}
for _, test := range tests {
head := ArrayToLink(test.nums)
head = RemoveNode(head, test.value)
array := LinkToArray(head)
fmt.Println(ArrayEqual(array, test.res))
}
}
如果你对算法感兴趣，可以看看我刷的LeetCode：https://github.com/chentaihan/leetcode （求赞）
如果你对算法感兴趣，可以看看我刷的LeetCode：https://github.com/chentaihan/leetcode （求赞）
如果你对算法感兴趣，可以看看我刷的LeetCode：https://github.com/chentaihan/leetcode （求赞）
