LeetCode100.删除链表的倒数第 N 个结点

1. 题目大意

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？

2. 思路分析

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

我们可以先遍历一遍链表求出链表的长度，再遍历时遇到倒数第n+1个，可以直接删除第n个。

接下来是进阶，上面的方法需要遍历两遍链表，如果遍历一次那?答：使用双指针，A指针在原地，另一个B指针距离上一个指针N个节点，当B指针为空的时，A指针恰好指向第N个节点。当然为了方便删除的操作，可以在列表前面加一个头节点，A从头节点开始计算，这样当B节点为空的时候，Ａ恰好指向倒数第Ｎ个节点的前一个节点。

3. 代码示例

Java版本

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode temp = head;int size = 0;while(temp!=null){temp = temp.next;size++;}if(size ==1){return null;}ListNode dummy = new ListNode(0, head);ListNode cur = dummy;for(int i=1; i<size-n+1; i++){cur = cur.next;}cur.next = cur.next.next;return dummy.next;}
}

Python版本

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:res = ListNode(0)cur = res# 保存进制记录carry = 0while l1 is not None or l2 is not None or carry:x = 0 if l1 is None else l1.valy = 0 if l2 is None else l2.valsum = x+y+carrycarry = sum // 10sum = sum % 10cur.next = ListNode(sum)cur = cur.nextif l1 is not None:l1 = l1.nextif l2 is not None:l2 = l2.nextreturn res.next