leetcode19: 删除链表的倒数第N个节点
2019-07-17 本文已影响0人
杨柳滔滔
题目
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
头节点的应用
(引用百度百科)
讲到链表不得不讲到头节点,数据结构中,在单链表的第一个结点之前附设一个结点,它没有直接前驱,称之为头结点
头结点是链表里面第一个结点,他的数据域可以不存放任何信息(有时候也会存放链表的长度等等信息),他的指针区域存放的是链表中第一个数据元素的结点(就是传说中的首元结点)存放的地址。
- 防止单链表是空的而设的.当链表为空的时候,带头结点的头指针就指向头结点.如果当链表为空的时候,头结点的指针域的数值为NULL.
- 是为了方便单链表的特殊操作,插入在表头或者删除第一个结点.这样就保持了单链表操作的统一性!
- 单链表加上头结点之后,无论单链表是否为空,头指针始终指向头结点,因此空表和非空表的处理也统一了,方便了单链表的操作,也减少了程序的复杂性和出现bug的机会 。
思路
- 链表的结构特殊,没有办法根据倒数位置直接定位到该位置的具体索引值,因为事先不知道链表的长度,如果设置一个快指针和慢指针,令他们的的距离为n,然后一起滑动,这样,当快指针到达终点的时候,慢指针下一个指向刚好就行需要删除的节点
- 设置一个头指针preNode,preNode.next=head
- 设置快指针fastNode=preNode,慢指针slowNode=preNode
- 循环n次,让fastNode前进n步
- 继续循环,直到fastNode到达链表尾端,这样慢节点的下一个节点刚好就是要删除的节点
图解
用ppt做的gif
图解算法.gif
代码
public class removeNthFromEnd {
public ListNode removeNthFromEndSolution(ListNode head, int n) {
ListNode preNode = new ListNode(0);
preNode.next = head;
ListNode fastNode = preNode, slowNode = preNode;
while (n > 0) {
fastNode = fastNode.next;// 采用快慢节点
n--;
}
while (fastNode.next != null) {
fastNode = fastNode.next;
slowNode = slowNode.next;// 快慢节点距离始终一致,等快节点到终点的时候,慢节点刚好落在了需要删除的那个节点上面
}
slowNode.next = slowNode.next.next;// 删除节点
return preNode.next;
}
}