1.算法题目
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
通过次数131,025提交次数3
2.算法思路
双链表法：可以通过遍历一次链表，也不需要计算链表的长度，即可找到要删除的节点，具体思路：定义两个链表 firstNode 和 secondNode ，初始化时都指向头节点，删除链表的倒数第 n 个节点时需要找到倒数第 n + 1 个节点，先遍历 firstNode，firstNode 遍历到 n + 1 个节点的时候再开始遍历 secondNode，当firstNode遍历到尾结点的时候，secondNode 刚好遍历到倒数
n + 1 个节点的位置，此时删除 secondNode 的下一个节点即可。需要注意的是链表只有一个节点的特殊情况，此时需要删除头节点。
3.算法代码
根据双链表法的算法思路编写的算法Java实现代码如下：
// 链表定义
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode firstNode = head;
ListNode secondNode = head;
while (firstNode != null && firstNode.next != null) {
firstNode = firstNode.next;
if(n == 0) {
secondNode = secondNode.next;
}
if (n > 0) {
n --;
}
}
if (n > 0) { // 删除当前节点
if (secondNode.next == null) { // 删除头节点
head = null;
} else { // 删除当前节点
head = head.next;
}
} else {
ListNode tmp = secondNode.next; // 待删除节点
secondNode.next = tmp.next;
}
return head;
}
4.总结
双链表法在有关链表的算法中比较常用，而且用起来很方便，比如判断一个链表是否有环、删除指定位置的节点、判断两个链表是否交叉（交叉的链表后面的节点都是一样的，可以让长度长的链表先走两个链表长度只差的位置）等等。
附判断两个链表是否交叉的算法Java实现代码：
// 链表定义
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
//获取链表长度
private int getLength(ListNode head){
int len = 0 ;
/*
ListNode cur = head;
while(cur != null){
len ++;
cur = cur.next;
*/
for(ListNode cur =head;cur!= null;cur = cur.next){
len ++;
}
return len;
}
//判断交叉+求交叉结点
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = getLength(headA);
int lenB = getLength(headB);
ListNode longer = headA;
ListNode shorter = headB;
int diff = lenA-lenB;
if(lenA < lenB){
diff = lenB-lenA;
longer = headB;
shorter = headA;
}
//让长链表先走diff步,保证下一步while值对比循环初始两个链表长度是相同的
for(int i = 0; i < diff; i++){
longer =longer.next;
}
//循环遍历，当值相等时停止循环
while(longer != shorter){
longer = longer.next;
shorter = shorter.next;
}
//返回交叉结点
return longer;
}
如果你有疑问或更好的算法思路，欢迎留言交流！！！
如果感觉我的文章对您有所帮助，麻烦动动小手给个喜欢，谢谢！！！
网友评论