题目：
给定一个链表，删除链表的倒数第n个节点并返回链表的头指针
例如，
给出的链表为:1->2->3->4->5, n= 2.↵↵ 删除了链表的倒数第n个节点之后,链表变为1->2->3->5.
备注：
题目保证n一定是合法的
请尝试只用一步操作完成该功能
思路：
1.用两个节点，删除让前一个节点比后一个节点先跑n次，然后两个一起跑。
2.当前一个节点遍历结束或者为空的时候，后一个节点是要删除的元素，但是要删除一个元素，必须知道它的前一个节点，。
3.遍历的时候就不用等到最后一个节点为空，可以在最后一个节点的next域为空的时候结束循环后一个节点的指向的下一个元素就是要删除的元素，将其删除即可
代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//当链表为空或者要删除的节点小于等于0的时候，直接返回head
if (head == null || n <= 0)
return head;
//建立一个虚拟的表头结点，因为需要删除的节点有可能是头结点，
// 所以建立虚拟头结点可以不用分是否是头结点两种情况
ListNode tempHead = new ListNode(0);
tempHead.next = head;
ListNode p = tempHead, q = tempHead;
//p指针比q指针先跑n次
for (int i = 0; i < n; i++) {
//如果p为空的时候，说明这个节点的长度不足n，返回head
if (p == null )
return head;
else {
p = p.next;
}
}
//p，q一起往前跑，直到p的next为空，
// q所指向的下一个结点就是要删除的元素的位置
while (p.next != null) {
p = p.next;
q = q.next;
}
//删除q指向的节点的下一个元素
q.next = q.next.next;
//删除虚拟头结点
return tempHead.next;
}
}
网友评论