刪除單鏈表，你會嗎？

刪除單鏈表中值等于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

posted @ 2019-12-19 13:25 古文觀芷閱讀(959) 評論(0) 收藏舉報

刷新頁面返回頂部

刪除單鏈表，你會嗎？

公告