LeetCode第十九题：删除链表的倒数第 N 个结点

admin
学习
2024-03-07
54热度
0评论

题目来源：LeetCode第十九题

1.题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

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

输出：[1,2,3,5]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

2.解题思路

解法一：双遍历法

描述：从头节点开始遍历整个链表以确定链表的总长度L。计算要删除的节点在链表中的正向位置，即L - n + 1。从头节点开始遍历链表，直到达到要删除节点的前一个节点（即第L - n个节点）。修改前一个节点的next指针，让它指向要删除节点的下一个节点，从而达到删除节点的目的。
时间复杂度：O(L)。其中L是链表的长度。
空间复杂度：O(1)。额外使用的空间主要是几个指针变量（例如用于遍历链表的指针），其空间占用是常数级的。
参考代码：

java版：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建一个哨兵节点，它的next指针指向链表头部
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 第一次遍历，计算链表长度
        int length = 0;
        ListNode first = head;
        while (first != null) {
            length++;
            first = first.next;
        }
        // 找到要删除节点的前一个节点的位置
        length -= n;
        // 从哨兵节点开始遍历
        first = dummy;
        while (length > 0) {
            length--;
            first = first.next;
        }
        // 这里first已经到了要删的节点的前面
        // 删除节点
        first.next = first.next.next;
        // 返回头节点
        return dummy.next;
    }
}

C++版：

class Solution {
public:
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		// 创建哨兵节点，并指向头节点
		ListNode* dummy = new ListNode(0);
		dummy->next = head;

		// 第一次遍历链表，计算总长度
		int length = 0;
		ListNode* first = head;
		while (first != NULL) {
			length++;
			first = first->next;
		}
		// 找到要删除节点的前一个节点的位置
		length -= n;
		// 从哨兵节点开始遍历
		first = dummy;
		while (length > 0) {
			length--;
			first = first->next;
		}
		// 这里first已经到了要删的节点的前面
		// 新建一个新节点指向要删的节点
		// 删除节点
		ListNode* nodeToDelete = first->next;
		first->next = nodeToDelete->next;
		// 释放被删除节点的内存
		delete nodeToDelete;
		//新建新的头节点
		ListNode* newHead = dummy->next;
		// 释放哨兵节点的内存
		delete dummy;
		// 返回新的头节点
		return newHead;
	}
};

C版：

// 删除链表的倒数第n个节点
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
	// 创建一个哨兵节点来简化某些边界情况的处理
	struct ListNode dummy;
	dummy.next = head;

	// 第一次遍历：计算链表的总长度
	int length = 0;
	struct ListNode* current = head;
	while (current != NULL) {
		length++;
		current = current->next;
	}

	// 找到要删除的节点的前一个节点
	length -= n;
	current = &dummy;
	while (length > 0) {
		current = current->next;
		length--;
	}

	// 删除节点，并释放内存
	struct ListNode* nodeToDelete = current->next;
	current->next = nodeToDelete->next;
	free(nodeToDelete); // 重要：释放被删除节点的内存

	return dummy.next;
}

解法二：双指针法(快慢指针)

描述：创建一个哨兵节点（dummy node），并将其next指针指向链表的头节点。这样做的目的是简化边界条件的处理，特别是当需要删除的节点是头节点时。初始化两个指针，快指针（fast）和慢指针（slow），让它们都指向哨兵节点。将快指针向前移动n + 1步，以保证快慢指针之间有n个节点的距离。同时向前移动快慢指针，直到快指针到达链表的末尾（即fast->next == NULL）。这时，慢指针将指向倒数第n+1个节点，即要删除节点的前一个节点。修改慢指针的next指针，使其跳过下一个节点（即要删除的节点），从而实现删除操作。返回哨兵节点的next节点，即新的头节点。
时间复杂度：O(L)。其中L是链表的长度。
空间复杂度：O(1)。使用了几个额外的指针变量（快指针、慢指针和哨兵节点），但这些变量是常数级别的。
参考代码：

java版：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建哨兵节点，并初始化快慢指针
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // D -> 1 -> 2 -> 3 -> 4 -> 5
        // ↑
        // fast, slow
        ListNode fast = dummy, slow = dummy;
        // 快指针先前进n+1步
        // D -> 1 -> 2 -> 3 -> 4 -> 5
        // ↑..............↑
        // slow......... fast
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        // 同时移动快慢指针
        // D -> 1 -> 2 -> 3 -> 4 -> 5 -> null
        // ...............↑..............↑
        // ..............slow............fast
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 最后慢指针到了要删节点的前一个节点
        // 进行删除节点操作
        slow.next = slow.next.next;

        return dummy.next;
    }
}

C++版：

class Solution {
public:
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		// 创建一个哨兵节点（dummy node），以简化边界条件处理
		// 例子D -> 1 -> 2 -> 3 -> 4 -> 5，n等于2
		ListNode* dummy = new ListNode(0);
		dummy->next = head;
		// 初始化快慢指针，都指向哨兵节点
		// D -> 1 -> 2 -> 3 -> 4 -> 5
		// ↑
		// fast, slow
		ListNode* fast = dummy, * slow = dummy;
		// 快指针先向前移动n+1步，保证快慢指针之间的距离为n
		// D -> 1 -> 2 -> 3 -> 4 -> 5
		// ↑..............↑
		// slow......... fast
		for (int i = 0; i <= n; i++) {
			fast = fast->next;
		}
		// 同时移动快慢指针
		// D -> 1 -> 2 -> 3 -> 4 -> 5 -> null
		// ...............↑..............↑
		// ..............slow............fast
		while (fast != nullptr) {
			fast = fast->next;
			slow = slow->next;
		}
		// 删除倒数第n个节点：修改慢指针的下一个指针，跳过下一个节点
		ListNode* nodeToDelete = slow->next;
		slow->next = slow->next->next;
		// 如果删除的是头节点，需要更新head
		ListNode* newHead = dummy->next;
		// 释放被删除节点的内存
		delete nodeToDelete;
		// 释放哨兵节点的内存
		delete dummy;
		// 返回新的头节点
		return newHead;
	}
};

C版：

// 函数：创建新的链表节点
struct ListNode* createNode(int val) {
	struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (newNode == NULL) {
		printf("Memory allocation failed\n");
		exit(1); // 如果内存分配失败，则退出程序
	}
	newNode->val = val;
	newNode->next = NULL;
	return newNode;
}

// 函数：删除链表的倒数第n个节点
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
	// 创建一个哨兵节点来简化边界条件的处理
	struct ListNode* dummy = createNode(0);
	dummy->next = head;

	struct ListNode* fast = dummy, * slow = dummy;

	// 快指针先向前移动n+1步
	for (int i = 0; i <= n; ++i) {
		fast = fast->next;
	}

	// 同时移动快慢指针直到快指针到达链表末尾
	while (fast != NULL) {
		fast = fast->next;
		slow = slow->next;
	}

	// 此时，慢指针指向的是要删除节点的前一个节点
	struct ListNode* nodeToDelete = slow->next;
	slow->next = nodeToDelete->next;

	// 释放被删除节点的内存
	free(nodeToDelete);

	// 更新头节点
	struct ListNode* newHead = dummy->next;
	// 释放哨兵节点的内存
	free(dummy);

	return newHead;
}

解法三：栈法

描述：首先，创建一个栈来存储链表的所有节点。遍历整个链表，将每个节点的指针依次推入栈中。这样，栈顶元素对应于链表的最后一个节点，而栈底元素对应于链表的第一个节点。通过从栈中弹出n个元素，我们可以到达倒数第n个节点的位置。由于栈是后进先出的，弹出n个元素后，当前栈顶元素即为倒数第n个节点的前一个节点。一旦找到倒数第n个节点的前一个节点，我们就可以修改其next指针，使其指向要删除节点的下一个节点，从而达到删除操作的目的。如果删除的是头节点，那么新的头节点将是哨兵节点的下一个节点。否则，头节点不变。
时间复杂度：O(L)。其中L是链表的长度。
空间复杂度：O(L)。主要是栈的空间消耗。栈需要存储整个链表的所有节点的指针。
参考代码：

java版：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        Stack<ListNode> stack = new Stack<>();
        // 创建哨兵节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 将所有节点压入栈中，包括哨兵节点
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        // 弹出n个元素，到达需要删除节点的前一个节点
        for (int i = 0; i < n; i++) {
            stack.pop();
        }
        // 删除倒数第n个节点
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        // 返回哨兵节点的下一个节点，即新的头节点
        return dummy.next;
    }
}

C++版：

class Solution {
public:
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		// 创建一个哨兵节点，并让它的next指向链表头节点，简化删除操作，特别是删除头节点的情况
		ListNode* dummy = new ListNode(0);
		dummy->next = head;
		// 使用栈存储从头节点到尾节点的所有节点指针
		stack<ListNode*> nodes;
		ListNode* current = dummy;
		while (current) {
			nodes.push(current);
			current = current->next;
		}

		for (int i = 0; i < n; i++) {
			nodes.pop();
		}
		// 此时栈顶元素是倒数第n个节点的前一个节点
		ListNode* prev = nodes.top();
		ListNode* nodeToDelete = prev->next;
		// 删除倒数第n个节点
		prev->next = nodeToDelete->next;
		// 如果倒数第n个节点是头节点，更新头节点
		ListNode* newHead = dummy->next;
		// 释放哨兵节点和要删除的节点的内存
		delete dummy;
		delete nodeToDelete;

		return newHead;
	}
};

C版：

// 栈的定义
struct Stack {
	struct ListNode** items; // 动态数组，用于存储链表节点的地址
	int top; // 栈顶位置
	int capacity; // 栈的容量
};

// 创建栈
struct Stack* createStack(int capacity) {
	struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
	stack->items = (struct ListNode**)malloc(sizeof(struct ListNode*) * capacity);
	stack->top = -1;
	stack->capacity = capacity;
	return stack;
}

// 检查栈是否满
int isFull(struct Stack* stack) {
	return stack->top == stack->capacity - 1;
}

// 检查栈是否为空
int isEmpty(struct Stack* stack) {
	return stack->top == -1;
}

// 入栈
void push(struct Stack* stack, struct ListNode* item) {
	if (isFull(stack)) {
		return; // 栈满，不做操作（实际应用中可能需要扩容）
	}
	stack->items[++stack->top] = item;
}

// 出栈
struct ListNode* pop(struct Stack* stack) {
	if (isEmpty(stack)) {
		return NULL; // 栈空，返回空
	}
	return stack->items[stack->top--];
}

// 获取栈顶元素
struct ListNode* peek(struct Stack* stack) {
	if (isEmpty(stack)) {
		return NULL;
	}
	return stack->items[stack->top];
}

// 删除链表的倒数第n个节点
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
	int capacity = 100; // 假设链表长度不超过100，实际应用中可能需要动态调整
	struct Stack* stack = createStack(capacity);

	struct ListNode dummy; // 创建哨兵节点
	dummy.next = head;

	struct ListNode* current = &dummy;
	while (current != NULL) {
		push(stack, current); // 将节点地址入栈
		current = current->next;
	}

	// 出栈n个元素，定位到倒数第n个节点的前一个节点
	for (int i = 0; i < n; ++i) {
		pop(stack);
	}

	struct ListNode* prev = pop(stack); // 倒数第n个节点的前一个节点
	prev->next = prev->next->next; // 删除节点

	free(stack->items); // 释放栈的动态数组
	free(stack); // 释放栈

	return dummy.next; // 返回修改后的链表头节点
}

解法四：递归法

描述：首先创建一个哨兵（dummy）节点，它的next指针指向链表的头节点。从哨兵节点开始，递归地遍历链表直到最后一个节点（即当node->next == null时递归到底）。在递归的回溯阶段，开始从链表末尾计数，每返回一层递归计数加1。当计数等于n + 1时，意味着找到了需要删除节点的前一个节点。通过修改这个节点的next指针，将其指向next->next节点，即可跳过需要删除的节点，从而实现删除操作。递归完成后，返回哨兵节点的下一个节点作为新的头节点。
时间复杂度：O(L)。L是链表的长度。
空间复杂度：O(L)。
参考代码：

java版：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // dummy节点用来处理边缘情况，例如当需要删除的是头节点时
        // dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 递归删除节点
        removeNode(dummy, n);
        // 返回新的头节点
        return dummy.next;
    }

    // 递归函数，返回从当前节点开始的倒数序号
    private int removeNode(ListNode node, int n) {
        // 如果当前节点是最后一个节点，则其倒数序号为1
        // dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
        // .............................↑
        // ..........................返回1就是倒数第一个
        if (node.next == null) {
            return 1;
        }
        // 递归调用并计数
        // count说的是当前节点是倒数第几个
        int count = removeNode(node.next, n) + 1;
        // 如果计数为n+1，说明当前节点是需要删除节点的前一个节点
        // dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
        // ........................↑....↑
        // ....................count=2..计数1
        // dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
        // ...................↑....↑
        // ................ c=3...c=2
        if (count == n + 1) {
            // 删除下一个节点
            node.next = node.next.next;
        }
        // 返回计数
        return count;
    }
}

C++版：

class Solution {
public:
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		// dummy节点用来处理边缘情况，例如当需要删除的是头节点时
		// dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
		ListNode* dummy = new ListNode(0);
		dummy->next = head;

		// 调用递归函数并传入哨兵节点，以便能够方便地处理头节点的删除
		removeNthFromEndRecursive(dummy, n);

		// 保存新的头节点，可能在删除第一个节点后发生变化
		ListNode* newHead = dummy->next;
		// 释放哨兵节点的内存
		delete dummy;
		return newHead;
	}

private:
	// 递归函数返回从当前节点开始的倒数序号
	int removeNthFromEndRecursive(ListNode* node, int n) {
		// 如果当前节点是最后一个节点，则其倒数序号为1
		// dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
		// .............................↑
		// ..........................返回1就是倒数第一个
		if (!node->next) return 1;
		// 递归调用并计数
		// count说的是当前节点是倒数第几个
		int count = removeNthFromEndRecursive(node->next, n) + 1;
		// 如果计数为n+1，当前节点是要删除节点的前一个节点
		// dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
		// ........................↑....↑
		// ....................count=2..计数1
		// dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
		// ...................↑....↑
		// ................ c=3...c=2
		if (count == n + 1) {
			// 保存要删除的节点
			ListNode* temp = node->next;
			// 删除操作
			node->next = node->next->next;
			// 释放被删除节点的内存
			delete temp;
		}
		// 返回包含当前节点在内的倒数序号
		return count;
	}
};

C版：

// 递归辅助函数
int removeNthFromEndHelper(struct ListNode* node, int n) {
	if (!node->next) {
		return 1; // 基准情况：到达链表末尾
	}

	int count = removeNthFromEndHelper(node->next, n) + 1;
	if (count == n + 1) { // 找到需要删除节点的前一个节点
		struct ListNode* temp = node->next;
		node->next = node->next->next;
		free(temp); // 释放被删除节点的内存
	}

	return count; // 返回包含当前节点在内的倒数序号
}

// 主要功能函数，删除链表的倒数第n个节点
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
	struct ListNode dummy; // 使用栈上的哨兵节点，无需手动释放
	dummy.val = 0;
	dummy.next = head;

	removeNthFromEndHelper(&dummy, n);

	struct ListNode* newHead = dummy.next;
	return newHead;
}