链表04-删除倒数第n个节点

Posted on Edited on

​ 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点，注意时间复杂度要求是O(n)

我心目中最经典的快慢指针例题

想要只遍历一遍链表找到倒数第n个节点，双指针的意义就在优化时间复杂度

大概思路就是 先来一个快指针走n步，随后慢指针同步从头节点出发，等到快指针走出链表为空时，慢指针此时所在的位置就是我们想要找的倒数第n个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 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):
    	dummy=ListNode(next=head)
        fast=dummy
        slow=dummy
        # 这里有个坑  我们是要删除倒数第n个节点 而不是找到倒数第n个节点
        # 而我们前面提到删除节点是需要知道前一个节点  这里我们找倒数第n+1个节点就完美解决问题
        for i in range(n+1):
            fast=fast.next
        """
        	所有有关删除增加节点的链表操作 全部使用虚拟头节点！！！！
        """
        while fast:   # 这里是fast 不是fast.next   遍历链表的操作不熟悉！
            fast=fast.next
            slow=slow.next
       	slow.next=slow.next.next
        return dummy.next