删除单链表,你会吗?
程序员文章站
2022-06-05 18:16:31
删除单链表中值等于XXX的所有元素 不经意间看到了一个不同寻常的实现方法,觉得挺有意思,于是自己实现了一下,代码真的是简单明了跑得还贼快! 好,现在先在脑海中想想,你会怎么实现?这么简单,5秒钟后,你想到了解决方案,于是你决定验证你的思路,请继续往下看 定义链表节点结构如下: type ListNo ......
删除单链表中值等于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: (求赞)
如果你对算法感兴趣,可以看看我刷的leetcode: (求赞)
如果你对算法感兴趣,可以看看我刷的leetcode: (求赞)