[leetcode19] delete the penultimate node in the linked list

Personally to

Front and rear double pointers

subject

I'll give you a list , Delete the last of the linked list n Nodes , And return the head node of the list .

Example 1：

Input ：head = [1,2,3,4,5], n = 2
Output ：[1,2,3,5]
Example 2：

Input ：head = [1], n = 1
Output ：[]
Example 3：

Input ：head = [1,2], n = 1
Output ：[1]

Tips ：

The number of nodes in the list is sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

Advanced ： Can you try a scan implementation ？

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/remove-nth-node-from-end-of-list
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

class Solution {
    
public:
	/* The method is to define two pointers . The phase difference interval is constant n. And advance simultaneously in one traversal . Abbreviation: front and back double pointers */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
    
		/* First define a header node . Unified operation . The official name is dumb node , namely dummy*/
		ListNode* dummy = new ListNode(0, head);

		/* Define two pointers before and after one . The following pointer needs to go more than the previous pointer n+1 Time  *  Because after traversal . The back pointer finally points to null. You also need to ensure that the front pointer just points to the precursor of the deleted node .*/
		/* Be careful * Has a higher priority than int, Will first combine variables ,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;
		}

		/* Delete */
		front->next = front->next->next;

		/* Don't go back head, The node pointed to by this pointer may have been deleted */
		/* Benefits of defining header nodes . Unified operation . At the same time, it can accurately return the pointer corresponding to the first node . * That is, you don't need to maintain the head pointer alone . Choose between two operations */
		return dummy->next;
    }
};