19-删除链表的倒数第N个节点
访问量:610

一、题目

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

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

二、解法

思路:双指针p1、p2。p1从head开始往后遍历,p2从第n+1个节点开始往后遍历,当p2到达倒数第一个节点的时候,p1则到达了倒数n+1个节点。


/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 // 思路
 // 双指针
 // head开始遍历
 // p2 比 p1 提前n
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    if n== 0 {
        return head
    }

    p1 := head
    p2 := head
    for n > 0 {
        p2 = p2.Next
        n --
    }

    // 代表删除第一个节点
    if p2 == nil {
        head = head.Next
        return head
    }

    // p1和p2 每次都是往后移动,当p2为null的时候,即p1在倒数第n个节点
    for p2.Next != nil {
        p1 = p1.Next
        p2 = p2.Next
    }

    // 删除倒数第n个节点
    p1.Next = p1.Next.Next

    return head
}