[数据结构与算法]Leetcode 中等：19. 删除链表的倒数第N个节点

题目：删除链表的倒数第N个节点

• 题号：19
• 难度：中等
• https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

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

示例1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例2：

输入：head = [1], n = 1
输出：[]

示例3：

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

进阶：

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

实现

第一种：先求链表长度的方法

思路：先求出链表的长度len，再求出要删除结点的位置index = len - n。这样就可以从头结点开始遍历到该位置，删除该结点即可。

C# 语言

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */

public class Solution
{
    public ListNode RemoveNthFromEnd(ListNode head, int n)
    {
        int len = GetLength(head);
        int index = len - n;

        if (index == 0)
        {
            head = head.next;
            return head;
        }
        ListNode temp = head;
        for (int i = 0; i < index - 1; i++)
        {
            temp = temp.next;
        }
        temp.next = temp.next.next;
        return head;
    }

    public int GetLength(ListNode head)
    {
        ListNode temp = head;
        int i = 0;
        while (temp != null)
        {
            i++;
            temp = temp.next;
        }
        return i;
    }
}

Python 语言

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        index = self.GetLength(head) - n
        if index == 0:
            head = head.next
            return head
        temp = head
        for i in range(index - 1):
            temp = temp.next
        temp.next = temp.next.next
        return head

    def GetLength(self, head):
        temp = head
        i = 0
        while temp != None:
            i += 1
            temp = temp.next
        return i

第二种：利用双指针的方式

思路： 使用两个指针，前面的指针p1先走n步，接着让后面的指针p2与p1同步走，p1走到终点，p2即走到要移除的结点位置。

C# 语言

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution 
{
    public ListNode RemoveNthFromEnd(ListNode head, int n) 
    {
        ListNode p1 = head;
        ListNode p2 = head;
        
        while (n > 0)
        {
            p1 = p1.next;
            n--;
        }

        if (p1 == null) //移除头结点
        {
            return head.next;
        }
            
        while (p1.next != null)
        {
            p1 = p1.next;
            p2 = p2.next;
        }
            
        p2.next = p2.next.next;
        return head;
    }
}

Python 语言

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        p2 = head
        p1 = head
        while (n > 0):
            p1 = p1.next
            n -= 1

        if (p1 is None):  # 移除头结点
            return head.next

        while (p1.next):
            p2 = p2.next
            p1 = p1.next

        p2.next = p2.next.next
        return head