删除链表的倒数第N个节点
- 19.删除链表的倒数第N个节点
- 思路
- 其他语言版本
19.删除链表的倒数第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]
思路
双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
思路是这样的，但要注意一些细节。
分为如下几步：
-
首先这里我推荐大家使用虚拟头结点，这样方便处理删除实际头结点的逻辑，如果虚拟头结点不清楚，可以看这篇： 链表：听说用虚拟头节点会方便很多？
-
定义fast指针和slow指针，初始值为虚拟头结点，如图：
-
fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图：
-
fast和slow同时移动，直到fast指向末尾，如题：
-
删除slow指向的下一个节点，如图：
此时不难写出如下C++代码：
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* slow = dummyHead;ListNode* fast = dummyHead;while(n-- && fast != NULL) {fast = fast->next;}fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点while (fast != NULL) {fast = fast->next;slow = slow->next;}slow->next = slow->next->next; // ListNode *tmp = slow->next; C++释放内存的逻辑// slow->next = tmp->next;// delete nth;return dummyHead->next;}
};
其他语言版本
java:
public ListNode removeNthFromEnd(ListNode head, int n){ListNode dummyNode = new ListNode(0);dummyNode.next = head;ListNode fastIndex = dummyNode;ListNode slowIndex = dummyNode;//只要快慢指针相差 n 个结点即可for (int i = 0; i < n ; i++){fastIndex = fastIndex.next;}while (fastIndex.next != null){fastIndex = fastIndex.next;slowIndex = slowIndex.next;}//此时 slowIndex 的位置就是待删除元素的前一个位置。//具体情况可自己画一个链表长度为 3 的图来模拟代码来理解slowIndex.next = slowIndex.next.next;return dummyNode.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 removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:head_dummy = ListNode()head_dummy.next = headslow, fast = head_dummy, head_dummywhile(n>=0): #fast先往前走n+1步fast = fast.nextn -= 1while(fast!=None):slow = slow.nextfast = fast.next#fast 走到结尾后，slow的下一个节点为倒数第N个节点slow.next = slow.next.next #删除return head_dummy.next
Go:
/*** Definition for singly-linked list.* type ListNode struct {* Val int* Next *ListNode* }*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {dummyHead := &ListNode{}dummyHead.Next = headcur := headprev := dummyHeadi := 1for cur != nil {cur = cur.Nextif i > n {prev = prev.Next}i++}prev.Next = prev.Next.Nextreturn dummyHead.Next
}
JavaScript:
/*** @param {ListNode} head* @param {number} n* @return {ListNode}*/
var removeNthFromEnd = function(head, n) {let ret = new ListNode(0, head),slow = fast = ret;while(n--) fast = fast.next;while (fast.next !== null) {fast = fast.next; slow = slow.next};slow.next = slow.next.next;return ret.next;
};
TypeScript:
版本一（快慢指针法）：
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {let newHead: ListNode | null = new ListNode(0, head);//根据leetcode题目的定义可推断这里快慢指针均不需要定义为ListNode | null。let slowNode: ListNode = newHead;let fastNode: ListNode = newHead;while(n--) {fastNode = fastNode.next!; //由虚拟头节点前进n个节点时,fastNode.next可推断不为null。}while(fastNode.next) { //遍历直至fastNode.next = null， 即尾部节点。 此时slowNode指向倒数第n个节点。fastNode = fastNode.next;slowNode = slowNode.next!;}slowNode.next = slowNode.next!.next; //倒数第n个节点可推断其next节点不为空。 return newHead.next;
}
版本二（计算节点总数法）：
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {let curNode: ListNode | null = head;let listSize: number = 0;while (curNode) {curNode = curNode.next;listSize++;}if (listSize === n) {head = head.next;} else {curNode = head;for (let i = 0; i < listSize - n - 1; i++) {curNode = curNode.next;}curNode.next = curNode.next.next;}return head;
};
版本三（递归倒退n法）：
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {let newHead: ListNode | null = new ListNode(0, head);let cnt = 0;function recur(node) {if (node === null) return;recur(node.next);cnt++;if (cnt === n + 1) {node.next = node.next.next;}}recur(newHead);return newHead.next;
};
Kotlin:
fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {val pre = ListNode(0).apply {this.next = head}var fastNode: ListNode? = prevar slowNode: ListNode? = prefor (i in 0..n) {fastNode = fastNode?.next}while (fastNode != null) {slowNode = slowNode?.nextfastNode = fastNode.next}slowNode?.next = slowNode?.next?.nextreturn pre.next
}
Swift：
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {if head == nil {return nil}if n == 0 {return head}let dummyHead = ListNode(-1, head)var fast: ListNode? = dummyHeadvar slow: ListNode? = dummyHead// fast 前移 nfor _ in 0 ..< n {fast = fast?.next}while fast?.next != nil {fast = fast?.nextslow = slow?.next}slow?.next = slow?.next?.nextreturn dummyHead.next
}
PHP:
function removeNthFromEnd($head, $n) {// 设置虚拟头节点$dummyHead = new ListNode();$dummyHead->next = $head;$slow = $fast = $dummyHead;while($n-- && $fast != null){$fast = $fast->next;}// fast 再走一步，让 slow 指向删除节点的上一个节点$fast = $fast->next; while ($fast != NULL) {$fast = $fast->next;$slow = $slow->next;}$slow->next = $slow->next->next;return $dummyHead->next;}
Scala:
object Solution {def removeNthFromEnd(head: ListNode, n: Int): ListNode = {val dummy = new ListNode(-1, head) // 定义虚拟头节点var fast = head // 快指针从头开始走var slow = dummy // 慢指针从虚拟头开始头// 因为参数 n 是不可变量，所以不能使用 while(n>0){n-=1}的方式for (i <- 0 until n) {fast = fast.next}// 快指针和满指针一起走，直到fast走到nullwhile (fast != null) {slow = slow.nextfast = fast.next}// 删除slow的下一个节点 slow.next = slow.next.next// 返回虚拟头节点的下一个dummy.next}
}
Rust:
impl Solution {pub fn remove_nth_from_end(head: Option<Box<ListNode>>, mut n: i32) -> Option<Box<ListNode>> {let mut dummy_head = Box::new(ListNode::new(0));dummy_head.next = head;let mut fast = &dummy_head.clone();let mut slow = &mut dummy_head;while n > 0 {fast = fast.next.as_ref().unwrap();n -= 1;}while fast.next.is_some() {fast = fast.next.as_ref().unwrap();slow = slow.next.as_mut().unwrap();}slow.next = slow.next.as_mut().unwrap().next.take();dummy_head.next}
}
C语言
/**c语言单链表的定义* Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {//定义虚拟头节点dummy 并初始化使其指向headstruct ListNode* dummy = malloc(sizeof(struct ListNode));dummy->val = 0;dummy->next = head;//定义 fast slow 双指针struct ListNode* fast = head;struct ListNode* slow = dummy;for (int i = 0; i < n; ++i) {fast = fast->next;}while (fast) {fast = fast->next;slow = slow->next;}slow->next = slow->next->next;//删除倒数第n个节点head = dummy->next;free(dummy);//删除虚拟节点dummyreturn head;
} 
