删除链表的倒数第n个节点

1. 题目描述

给定一个链表，删除链表的倒数第n个节点并返回链表的头指针 例如， 给出的链表为:1->2->3->4->5, n= 2. 删除了链表的倒数第n个节点之后,链表变为1->2->3->5.

2. 思路

1. 思路一
   • 遍历一遍计数，第二遍走到 count-n 节点
2. 思路二
   • 双指针
   • 一个指针先走n步
   • 两个指针一起走直到快指针走到末尾

3. 实现

3.1. 两次遍历

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    h := head
    count := 0
    for h != nil {
        count++
        h = h.Next
    }

    dummyHead := &ListNode{
        Next:head,
    }
    h = dummyHead
    for i := 0; i < count-n; i++{
        h  = h.Next
    }
    delNode := h.Next
    h.Next = delNode.Next
    delNode.Next = nil
    return dummyHead.Next
}

3.2. 双指针

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {

    dummyHead := &ListNode{Next:head}
    fast := dummyHead
    for i:= 0; i < n; i++ {
        fast = fast.Next
    }
    slow := dummyHead
    for fast != nil && fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }
    slow.Next = slow.Next.Next
    return dummyHead.Next

}

4. 参考

• 删除链表的倒数第n个节点_牛客题霸_牛客网
• 19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）