字节跳动校招秋招算法面试真题解题报告--leetcode19 删除链表的倒数第 n 个结点，内含7种语言答案
1.题目描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
2.解题报告
在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 \textit{next}next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。
例如，在本题中，如果我们要删除节点 yy，我们需要知道节点 yy 的前驱节点 xx，并将 xx 的指针指向 yy 的后继节点。但由于头节点不存在前驱节点，因此我们需要在删除头节点时进行特殊判断。但如果我们添加了哑节点，那么头节点的前驱节点就是哑节点本身，此时我们就只需要考虑通用的情况即可。
这个题目是双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
3.最优答案
c答案
/*** Definition for singly-linked list.* struct ListNode {*int val;*struct ListNode *next;* };*///定义两个指针，刚开始分别指向头结点，然后先让一个指针先走n-1步，接着两个指针同时遍历链表，当第一个指针到达链表尾部的时候，第二个指针指向的就是要删除的倒数第n个结点。 struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {struct ListNode *fast=head;struct ListNode *slow=head;for(int i=0;i<n;i++){fast=fast->next;if(fast==NULL) return head->next;}while(fast->next !=NULL){fast=fast->next;slow=slow->next;}slow->next=slow->next->next;return head;// struct ListNode *fast=head;// struct ListNode *slow=head;// int i;// for(i=0;i<n;i++)// {//fast=fast->next;//if(fast == NULL) return head->next; // }// while(fast->next != NULL)// {//fast=fast->next;//slow=slow->next;// }// slow->next=slow->next->next;// return head;}
c++答案
class Solution {public:ListNode* removeNthFromEnd(ListNode* head, int n) {if (!head->next) return NULL;//空链表ListNode *pre = head, *cur = head;for (int i = 0; i < n; i++)cur = cur->next;if (!cur)return head->next;//cur==NULL，此时n大于链表长度，返回首元素while (cur->next){cur = cur->next;pre = pre->next;//cur先走了n个长度，领先pre了n个长度;所以当cur走到末尾时，pre刚好指向倒数第n个节点}pre->next = pre->next->next;return head;}};
java答案
/*** Definition for singly-linked list.* public class ListNode {*int val;*ListNode next;*ListNode(int x) { val = x; }* }*/class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode root =head;HashMap<Integer,ListNode> map = new HashMap<>();int count = 0;while(head != null){count += 1;map.put(count,head);head = head.next;}if(count == 1 || count == n){root = root.next;}else if(n == 1 && count ==2){map.get(count - n ).next = null;}else {map.get(count - n ).next = map.get(count - n + 2);}return root;}}
JavaScript答案
/*** Definition for singly-linked list.* function ListNode(val) {*this.val = val;*this.next = null;* }*//*** @param {ListNode} head* @param {number} n* @return {ListNode}*/var removeNthFromEnd = function(head, n) {if(head == null || n <= 0) {return head;}var dummy = new ListNode(0);dummy.next = head;var p = dummyvar q = dummyfor(var i = 0; i < n + 1; i++) {p = p.next;}while(p) {p = p.next;q = q.next}q.next = q.next.next;return dummy.next;// var count = 0;// var p = head;// while(p) {//count++//p = p.next// }// //顺数第m个// var m = count - n + 1;// var dummy = new ListNode(0);// dummy.next = head;// var cur = dummy;// for(var i = 1; i < m; i++) {//cur = cur.next;// }// cur.next = cur.next.next;// return dummy.next;};
c#答案
/*** Definition for singly-linked list.* public class ListNode {*public int val;*public ListNode next;*public ListNode(int x) { val = x; }* }*/public class Solution {public ListNode RemoveNthFromEnd(ListNode head, int n) {if(head==null)return null;var list=new List<ListNode>(){head};int i=0;while(i<list.Count){if(list[i].next!=null) {list.Add(list[i].next);}i++;}if(list.Count==1){return null;}else if(list.Count==n){return list[1];}i=list.Count-n;if(i>-1){if(n==1){list[list.Count-2].next=null;}else if(i-i>=0 && i+1<list.Count)list[i-1].next=list[i+1];}return list[0];}}
python2.x答案
# Definition for singly-linked list.# class ListNode(object):#def __init__(self, x):# self.val = x# self.next = Noneclass Solution(object):def removeNthFromEnd(self, head, n):""":type head: ListNode:type n: int:rtype: ListNode"""dummy = ListNode(0)dummy.next = headfirst = second = dummyfor i in range(n):first = first.nextwhile first.next:first = first.nextsecond = second.nextsecond.next = second.next.nextreturn dummy.next
python3.x答案
# Definition for singly-linked list.# class ListNode:#def __init__(self, x):# self.val = x# self.next = Noneclass Solution:def removeNthFromEnd(self, head, n):""":type head: ListNode:type n: int:rtype: ListNode"""head2 =[head.val]while head.next != None:head =head.nexthead2.append(head.val)head2.pop(-n)return head2
go答案
/*** Definition for singly-linked list.* type ListNode struct {*Val int*Next *ListNode* }*/func removeNthFromEnd(head *ListNode, n int) *ListNode {var arr []*ListNodearr = append(arr, head)for node := head; node.Next != nil; node = node.Next {arr = append(arr, node.Next)}if n == len(arr) {head = head.Next} else if n == 1 {del := arr[len(arr)-2]del.Next = nil} else {del := arr[len(arr)-n]deleteNode(del)}return head}func deleteNode(node *ListNode) {next := node.Nextnode.Val = next.Valnode.Next = next.Next}
4.算法面试宝典小程序
微信搜“算法面试宝典”，内含1000个算法题目的7种语言的top5答案和详细解题报告，无论是校招还是社招，让你算法面试中游刃有余，助力薪酬提升30%。
字节跳动校招秋招算法面试真题解题报告--leetcode19 删除链表的倒数第 n 个结点 内含7种语言答案
如果觉得《字节跳动校招秋招算法面试真题解题报告--leetcode19 删除链表的倒数第 n 个结》对你有帮助，请点赞、收藏，并留下你的观点哦！
