删除链表的倒数第N个节点,并返回链表的头节点

JAVA乐园

共 1126字,需浏览 3分钟

 ·

2021-01-28 21:47

面试的时候遇到了一个笔试题,是leetcode的原题,原题的连接:

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

大概的内容:删除链表的倒数第N个节点,并返回链表的头节点。

一开始遇到这个题也是一脸懵,通过查看解题思路才了解到有几种解决方式:

单向项链表实现类:

public class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
 }


0x01:两次循环求长度

实现思路:

1、先循环一遍链表,求出链表的长度L,倒数第N个节点就是从开头数第(L-N+1)个节点,将此节点的next指向下下节点就可以了。

在解题的过程中要添加一个亚节点(dummy)进行辅助(如:图1),D就是我们的亚节点。

图1

代码:

ListNode dummy = new ListNode(0);//亚节点
dummy.next = head;
int length = 0;
ListNode first = head;
//通过移动头节点循环求出链表的长度
while(first != null){
    length++;
    first=first.next;
}
length -= n;//计算要删除节点位置
first = dummy;
while(length > 0){
    length --;
    first = first.next;
}
first.next = first.next.next;
return dummy.next;//返回头节点


0x02:双指针

实现思路:

1、定义两个指针同时指向我们的亚节点。

2、第一个指针节点向前移动N+1步,第二个指针保持不动,这时两个指针相隔N个节点的距离

3、同时移动两个指针保持恒定的距离,直到第一个指针到达最后一个节点。

4、这时第二个指针所指向的节点的下一个节点就是要删除的节点(倒数第N个节点),将第二个指针指向的节点的next指向下下个节点就完成了。

图2

代码:

ListNode dummy = new ListNode(0);//亚节点
dummy.next = head;
ListNode first = dummy;//第一个指针
ListNode secound = dummy;//第二个指针
for(int i = 0; i//向前移动第一个之指针N+1
    first= first.next;
}
while(first != null){//同时移动第一个指针和第二个指针直到第一个指针指向null
    first = first.next;
    secound = secound.next;
}
secound.next = secound.next.next;
return dummy.next;

我们能看到方法二比方法一代码简洁一些,双指针也是算法题里面比较常用的解题方法。

仔细查看评论区我们又看到不错的解题思路,使用递归方法和特性实现


0x03:递归的特性

实现思路:

1、利用递归调用的特性先循环一遍链表,相当于用指针从链表头走到链表尾(如:图3-2)

2、递归调用在调用自身方法后面会倒叙的循环调用,相当于指针在从尾节点执行到头节点,这时在第N步将指针指向的节点的next指向下下个节点就完成了。

这里递归的特性和使用会在后面单独写一篇文章来说明。

图3-1

图3-2

代码:

public static ListNode removeNthFromEnd(ListNode head, int n{
     int pos = helper(head, n);
     // 说明删除的是头节点
      if(pos == n - 1) {
            return head.next;
        }
        return head;
    }
// 获取节点所在位置,逆序
    public int helper(ListNode node, int n{
        if(node.next == null) {
            return 0;
        }
        int pos = helper(node.next, n) + 1;
        if(pos == n) {
            node.next = node.next.next;
        }
        return pos;
    }


source:https://www.cnblogs.com/stevewys/articles/13252439.html

喜欢,在看



浏览 16
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报