[leetcode19]删除链表中倒数第n个结点

个人向

前后双指针

题目

给你一个链表，删除链表的倒数第 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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    
public:
	/*方法就是定义两个指针。相差间隔恒定为n。并且在一次遍历中同时前进。简称前后双指针*/
    ListNode* removeNthFromEnd(ListNode* head, int n) {
    
		/*先定义一个头结点。统一操作。官方的称呼是哑结点，即dummy*/
		ListNode* dummy = new ListNode(0, head);

		/*定义一前一后两个指针。需要后面的指针比前面的指针多走n+1次 * 因为遍历一遍之后。后指针最终指向null。还需要保证前指针正好指向被删除结点的前驱。*/
		/*注意*的优先级高于int,会先结合变量，listnode (*a) */
		ListNode* front = dummy, * back = dummy;
		for (int i = 1; i <= n + 1; i++)
			back = back->next;

		while (back) {
    
			front = front->next;
			back = back->next;
		}

		/*删除*/
		front->next = front->next->next;

		/*别返回head,该指针指向的结点可能已经被删除了*/
		/*定义头结点的好处。统一操作。同时可以准确返回第一个结点对应的指针。 *即不用自己单独维护头指针了。两种操作二选一*/
		return dummy->next;
    }
};