2021-02-09：如何删除一个链表的倒数第n个元素？

福大大架构师每日一题 · · 741 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

福哥答案2021-02-09：

1.创建虚拟头元素，虚拟头元素的Next指针指向头元素。
2.根据快慢指针求倒数第n+1个元素，假设这个元素是slow。
3.设置元素slow的Next指针。slow.Next=slow.Next.Next。
4.返回虚拟头元素的Next指针。

代码用golang编写，代码如下：

package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func main() {
    head := &ListNode{}
    head.Val = 1

    head.Next = &ListNode{}
    head.Next.Val = 2

    head.Next.Next = &ListNode{}
    head.Next.Next.Val = 3

    head.Next.Next.Next = &ListNode{}
    head.Next.Next.Next.Val = 4

    ret := head
    for ret != nil {
        fmt.Print(ret.Val, " ")
        ret = ret.Next
    }

    fmt.Println("\r\n-------")
    k := 4
    fmt.Println("删除倒数第", k, "个元素后：")

    ret = DeleteNode(head, k)
    for ret != nil {
        fmt.Print(ret.Val, " ")
        ret = ret.Next
    }
}
func DeleteNode(head *ListNode, k int) *ListNode {
    preHead := &ListNode{}
    preHead.Next = head

    fast := preHead
    slow := preHead

    k++
    for k > 0 {
        fast = fast.Next
        k--
    }

    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }

    slow.Next = slow.Next.Next

    return preHead.Next
}

执行结果如下：