19. Remove Nth Node From End of List

1. 原始题目

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

2. 题目理解

删除列表中倒数第n个数

注意：空列表，和n大于链表长度的情况

3. 解题

改题和剑指offer中题23类似，其为寻找链表中倒数第n个结点。当然直观理解是先遍历一遍得到链表长度，再得到n在正数的位置，然后删除。

好的思路是遍历一遍。即引入两个指针，先让第一个指针走n步，然后两个指针再同时走，那么这两个指针间隔始终为n。当先走的指针走到链表末尾时，后走的指针正好在第n个元素位置上。那此时可以直接删除吗?不可以。因为直接删掉，链表就断裂了。所以可以在链表开始新建一个头结点，这时当先走的指针走到链表末尾时，后走的指针正好在要删除的元素的前一个位置，这时可以一条语句删除第n个元素啦。

 1 # Definition for singly-linked list.
 2 # class ListNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution:
 8     def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
 9         if not head:
10             return False
11         
12         p_behind = ListNode(0)    # 新建一个空结点。
13         p_behind.next = head
14         p_ahead = p_behind
15         newhead = p_behind        # 保持头结点  
16 
17         for k in range(n):        # 先走n步，看看是否链表长度至少大于n。否则取一个小于n的链表的倒数第n个元素没有意义。
18             if p_ahead.next:
19                 p_ahead = p_ahead.next
20             else:
21                 return False      # n不合理，返回False 
22                 
23         while p_ahead.next:       # 同步走    
24             p_behind = p_behind.next
25             p_ahead = p_ahead.next
26         
27         p_behind.next = p_behind.next.next   # 删除结点
28         
29         return newhead.next # 返回真正的头结点

验证：

 1 # 新建链表1
 2 listnode1 = ListNode_handle(None)
 3 s1 = [1,2,3,4,5]
 4 for i in s1:
 5     listnode1.add(i)
 6 listnode1.print_node(listnode1.head)
 7 
 8 s = Solution()
 9 head = s.removeNthFromEnd(listnode1.head, 1)
10 listnode1.print_node(head)

1 2 3 4 5 1 2 3 4