19.remove-nth-node-from-end-of-list.cpp

/*
 * @lc app=leetcode id=19 lang=cpp
 *
 * [19] Remove Nth Node From End of List
 *
 * https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
 *
 * algorithms
 * Medium (35.56%)
 * Likes:    4859
 * Dislikes: 288
 * Total Accepted:    806.3K
 * Total Submissions: 2.3M
 * Testcase Example:  '[1,2,3,4,5]\n2'
 *
 * Given the head of a linked list, remove the n^th node from the end of the
 * list and return its head.
 * 
 * Follow up: Could you do this in one pass?
 * 
 * 
 * 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]
 * 
 * 
 * 
 * Constraints:
 * 
 * 
 * The number of nodes in the list is sz.
 * 1 <= sz <= 30
 * 0 <= Node.val <= 100
 * 1 <= n <= sz
 * 
 * 
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd1(ListNode* head, int n) {
        ListNode* node = head;
        while (n != 1) {
            node = node->next;
            n--;
        }
        ListNode* nthNode = head;
        ListNode* preN = nullptr;
        while (node->next != nullptr) {
            preN = nthNode;
            nthNode = nthNode->next;
            node = node->next;
        }
        if (preN == nullptr) {
            head = head->next;
            delete nthNode;
            nthNode = nullptr;
        } else {
            preN->next = nthNode->next;
            delete nthNode;
        }
        return head;
    }
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* node = head;
        while (n != 1) {
            node = node->next;
            n--;
        }
        ListNode dummy(0);
        dummy.next = head;
        ListNode* nthNode = head;
        ListNode* preN = &dummy;
        while (node->next != nullptr) {
            preN = nthNode;
            nthNode = nthNode->next;
            node = node->next;
        }
        preN->next = nthNode->next;
        return dummy.next;
    }
};
// @lc code=end