原题
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
解法
思想
使用两个指针,让快指针一开始和慢指针保持n的距离,两者一起以同样速度移动,则当快指针指向链表的最后一个节点的时候,慢指针的下一个节点就是要删除的节点。
代码
HashSet:
/**
* 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 slow;
ListNode fast;
slow = fast = 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;
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode19-%e5%88%a0%e9%99%a4%e9%93%be%e8%a1%a8%e7%9a%84%e5%80%92%e6%95%b0%e7%ac%acn%e4%b8%aa%e8%8a%82%e7%82%b9/