每日算法：删除链表的倒数第N个节点

微信公众号：你好面试官
这里没有碎片化的知识，只有完整的知识体系。
专注于系统全面的知识点讲解，面试题目解析;
如果你觉得文章对你有帮助，欢迎关注、分享、赞赏。

今日题目

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

LeetCode地址

题目描述

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

示例：

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

Java解法：

 1/**
 2 * Definition for singly-linked list.
 3 * public class ListNode {
 4 *     int val;
 5 *     ListNode next;
 6 *     ListNode(int x) { val = x; }
 7 * }
 8 */
 9class Solution {
10    public ListNode removeNthFromEnd(ListNode head, int n) {
11         if(head == null)
12           return null;
13       ListNode dummyHead = new ListNode(0);
14       dummyHead.next = head;
15       ListNode fast = dummyHead,slow = dummyHead;
16
17       while(n>=0){
18           fast = fast.next;
19           n--;
20       }
21
22       while(fast != null){
23           slow = slow.next;
24           fast = fast.next;
25       }
26       slow.next = slow.next.next;
27       return dummyHead.next;
28    }
29}

Python解法：

 1# Definition for singly-linked list.
 2# class ListNode:
 3#     def __init__(self, x):
 4#         self.val = x
 5#         self.next = None
 6
 7class Solution:
 8    def removeNthFromEnd(self, head, n):
 9        """
10        :type head: ListNode
11        :type n: int
12        :rtype: ListNode
13        """
14        tmp=ListNode(0)
15        tmp.next=head 
16        x,y=tmp,tmp
17
18        for i in range(n+1):
19            y=y.next
20
21        while y:
22            x=x.next
23            y=y.next
24
25        x.next=x.next.next
26
27        return tmp.next