欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

删除单链表,你会吗?

程序员文章站 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: (求赞