链表-如何高效删除链表的倒数第N个节点

题目

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点

示例

给定一个链表: 1->2->3->4->5, 和 n = 2 当删除了倒数第二个节点后，链表变为 1->2->3->5

思考

你能尝试使用一趟扫描实现吗?（时间复杂度O(n),空间复杂度O(1)）

解法一

我相信很多人都明白链表要删除一个节点的做法是把要删除的节点的前驱节点指向要删除的节点的后驱节点，则完成删除一个节点的操作，如下图所示：我们删除节点为2数据，就是如此简单

我们知道，链表不像数组那样，没有下标，要想知道链表的长度，只能从链表的头部开始遍历直到结束来统计链表的长度，我们现在知道要删除链表倒数第N个节点，我们首先想到，要是知道链表长度就好了啊，看如下代码

//定义一个链表结构体
type ListNode struct {
     Val int
     Next *ListNode
}
//删除链表中倒数第N个节点
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    if head == nil{
        return nil
    }
    len := 0
    temp1,temp2 := head,head
    for temp1 != nil{
        len++W
        temp1 = temp1.Next
    }
    //倒数第n个就等正数的第（len-n）+1个
    m := len- n
    //如果m=0，则是删除链表的头节点
    if m == 0{
        //如果要删除的是头节点，则将头节点指到head.Next节点
        head = head.Next
        return head
    }
    for i:=0; i<=len-1;i++{
        //找到要删除节点的上一个节点
        //将这个节点的下一个指针指到要删除节点的下一个节点
        if i == m-1{
            next := temp2.Next
            temp2.Next = next.Next
            break;
        }
        temp2 = temp2.Next
    }
    return head
}

我们看上面的代码，对整个链表进行了两次for循环，第一次求出链表的长度，第二次用来找到要删除的倒数第n个元素，有没有更好的办法呢，只遍历一次？

解法二

解法一已经实现了我们想要的功能，我们回看上面的思考（只扫描一趟实现此功能），我们看这个问题的本质，倒数第n个就等正数的第（len-n）+1个,我们看下图：

分析上面的图声明三个变量，one,two两个指针变量,i是一个int变量,one和two指向链表的头节点，one开始遍历链表，每遍历一个节点，变量i进行加1，当变量i大于n时（就是倒数第n个，在这里n是2）也就是当one指向节点4时（变成红色），two开始移动，直到one.Next等于空遍历结束，这是我们看two是不是指向了倒数第二个节点之前的节点了。 原理很简单，利用双指针变量，前指针遍历到n时，后指针开始遍历，则for循环结束时，后指针刚好指到要删除的节点的前驱节点，看代码：

//定义一个链表结构体
type ListNode struct {
    Val int
    Next *ListNode
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    i:=0
    one,two := head,head
    for one.Next != nil{
        i++
        if i>n{
            two = two.Next
        }
        one = one.Next
    }
    //当n是倒数最大时（也就是正数第一个），i是不会大于n的
    //这其实删除的是链表的头节点
    if i< n{
        head = head.Next
        return head
    }
    //将要删除的节点的前驱节点指向要删除的节点的后
    next := two.Next
    two.Next = next.Next
    return head
}

好了，删除链表倒数第N个节点就分享到这里，有收获的帮忙关注，转发，点赞呗。