精华内容
下载资源
问答
  • 删除链表倒数第N个节点 1.问题 给定一个链表删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3-...

    删除链表倒数第N个节点

    1.问题
    给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
    示例:
    给定一个链表: 1->2->3->4->5, 和 n = 2.
    当删除了倒数第二个节点后,链表变为 1->2->3->5.
    2.算法
    暴力破解法:先计算得出链表的长度M,然后将链表长度和所给倒数位置相减,即loc=M-n-1,得出删除节点的前一个节点,然后就可以删除了。具体代码如下:

    /**
     * 链表节点的定义
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
    	 public ListNode removeNthFromEnd(ListNode head, int n) {
    		 if(head==null)
    			 return null;
    		 
    		 ListNode temp=head,pre=null;
    		 int listlong=0;
    		 
    		 while(temp!=null) { //求出链表长度
    			 listlong++;
    			 temp=temp.next;
    		 }
    		 //如果删除位置和链表长度一致,即可直接返回首节点的下一个节点
    		 if(listlong==n)	
    			 return head.next;
    		 
    		 temp=head; //重新回到首节点
    		 for (int i = 0; i < listlong-n-1; i++) {
    			temp=temp.next;
    		}
    		 pre=temp;
    		 temp=temp.next;
    		 pre.next=temp.next;
    		 
    		 return head;
    	 }
    }
    

    这样算法很容易得出时间复杂度是O(M),空间复杂度为O(1),只用了一个临时指针的空间。
    但是这样的话是两次遍历,因此这个算法可以进行优化,变成只需要一次遍历即可。
    优化算法:
    设定双指针P,Q,当指针P指向链表节点最后指向的null时,它与指针Q相隔的元素刚好为n个,那么指针Q的下一个节点就是我们刚好要删除的节点。如下图所示(图源来自于leetcode第19题的程序员吴师兄的解释,链接:动图图解以及C++代码):
    删除节点示意图
    代码如下:

    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode first = head;
            ListNode second = head;
            int i = 1;
            for (; i < n; i++) {	//移动p指针
                if (first != null) {
                    first = first.next;
                } else {
                    break;
                }
            }
    
            if (i < n) {	//如果i<n,说明n大于链表长度,不用删除
                return head;
            }
            //刚好n使链表的长度,则直接删除头节点即可
            if (first.next == null) { 
                head =  head.next;
            } else {
                first = first.next;	//使指针p和q之间相隔n个元素
                while (first.next != null) {
                    first = first.next;
                    second = second.next;
                }
                second.next = second.next.next;
            }
            return head;
        }
    }
    

    这样的时间复杂度也是O(M),空间复杂度也是O(1),但是它只需要一次遍历,因此对于长链表来说的话,这样的提升也是很大的。

    展开全文
  • 给定一个链表删除链表的倒数 n 个节点,并且返回链表的头结点。 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数个节点后,链表变为 1->2->3->5. note: n>=链表长度时...

    leetcode 题目:
    给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

    	给定一个链表: 1->2->3->4->5, 和 n = 2.
    	当删除了倒数第二个节点后,链表变为 1->2->3->5.
    	note: 
    		n>=链表长度时,删除头节点;n<=0时,不做任何操作。
    

    当第一个指针first 比第二个指针领先n步,然后两个指针同步前进,那么第一个指针到达链表尾部时,第二个指针即指向要删除的节点。如图:
    在这里插入图片描述

    ListNode* removeNthFromEnd(ListNode* head, int n) {
            if(!head || n <= 0) return head;
    
            ListNode *first = head;
            ListNode *second = head;
            ListNode *prev = NULL;
            for(int i = 0; i < n && first; ++i){
                first = first->next;
            }
    
            while(first){
                first = first->next;
                prev = second;
                second = second->next;
            }
            if(!prev){ // 删除头结点
            	head = head->next;
            } else {
            	prev->next = second->next;
            }
            delete second;
            return head;
        }
    

    删除prev指针的遍历

    令first指针到达链表尾部时,second指针指向删除节点的前一个节点,就可以遍历prev指针了。
    使用这种方法,我们需要在链表头添加一个dummy节点,用于处理删除节点为头结点的情况。
    在这里插入图片描述

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head || n <= 0) return head;
     2
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
    
        ListNode *first = dummy;
        ListNode *second = dummy;
    
        // n >= 链表size,删除头节点
        for(int i = 0; i < n+1 && first; ++i){
            first = first->next;
        }
    
        while(first){
            first = first->next;
            second = second->next;
        }
        ListNode *prev = second;
        second = second->next;
        prev->next = second->next;
        delete second;
        
        ListNode *ret = dummy->next;
        delete dummy;
        return ret;
    }
    
    展开全文
  • 删除的倒数第N个节点,也就是正序的(链表总长度len - N)个节点。 然后再遍历一次,直接删除目标节点即可。 代码: /** * Definition for singly-linked list. * public class ListNode { * int val; * ...

    题目:

    给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

    在这里插入图片描述

    解析:

    题目要求删除链表的节点。
    但是因为不能直接知道链表的长度,因此要先遍历一下链表,求出链表长度。
    要删除的倒数第N个节点,也就是正序的(链表总长度len - N)个节点。
    然后再遍历一次,直接删除目标节点即可。

    代码:

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {  
            int m=0;  //链表的总长度
            ListNode count=head;
            while(count!=null){  //遍历求长度
             m++;
            count=count.next;
            }
            ListNode new_head=new ListNode(-1);  //定义虚拟头结点
            new_head.next=head;
            ListNode pre=new_head;
            ListNode cur=head;
            int i=m-n;
            while(cur.next!=null && i>0){
               pre=pre.next;
               cur=cur.next;
                i--;
            }
            ListNode temp=cur.next;
            pre.next=cur.next;
            cur=temp;
            return new_head.next;    
        }
    }
    
    展开全文
  • 删除链表的倒数第N个节点 给定一个链表删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5...

    删除链表的倒数第N个节点

    给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

    示例:

    给定一个链表: 1->2->3->4->5, 和 n = 2.

    当删除了倒数第二个节点后,链表变为 1->2->3->5.

    说明:

    给定的 n 保证是有效的。

    进阶:

    尝试使用一趟扫描实现

    使用双指针a,b,a首先向后移动n-1次,此时b指针不动,当a指针移动n-1次后,b开始向后移动,当a遍历完毕时,b恰好指向要删除的节点

    代码实现:

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
            //双指针,a指针先走n-1步,b不动。b指针在a指针走n-1步之后从头开始走
            //当a指针遍历完时,b指针指向倒数第n个节点
            if(head->next==NULL)return NULL;
            ListNode *a=head;
            ListNode *b=head;
            ListNode *te=head;
            int count=0;
            while(a->next!=NULL)
            {
                count++;
                if(count>n-1)
                    b=b->next;
                if(count>n)
                    te=te->next;
                a=a->next;
            }
            if(b==head)head=head->next;
            else te->next=b->next;
            return head;
        }
    };
    
    

    在这里插入图片描述

    展开全文
  • 146-删除链表倒数第N个节点

    千次阅读 2021-01-22 11:36:06
    1、计算链表的长度,删除倒数第n个,就是删除倒数第len%n个节点 2、快慢指针均指向头结点,慢指针在头结点处不动,快指针向后走n个节点 3、如果此时快指针指向空,就是意味着要删除的是第一个结点,return head->...
  • 给定一个链表删除链表的倒数第n个节点并返回链表的头指针 例如, 给出的链表为:1->2->3->4->5, n= 2. 删除链表的倒数第n个节点之后,链表变为1->2->3->5. 题目保证n一定是有效的 请给出请给...
  • 2.删除链表倒数第N个节点 普通方法 ListNode *removeNthFromEnd(ListNode *head, int n) { if(head->next==nullptr) return nullptr; ListNode *first = head, *second = head; for (; n >...
  • 计算链表长度L,然后从头开始对链表进行遍历,当遍历到L-n+1个节点时,找到所要删除的节点。 代码如下: class Solution: def fun(self, head:ListNode, n): def getlength(head:ListNode): length = 0 while ...
  • 给定一个链表删除链表倒数第n个节点,并且返回链表的头结点。 示例: 给定一个链表:1->2->3->4->5,和 n = 2。当删除了倒数第二个节点后,链表变为 1->2->3->5。 说明: 给定的n保证是...
  • LeetCode19 删除链表倒数第n个节点 题目描述 给定一个链表删除链表中的倒数第n个节点,并且返回链表的头节点 说明:给定的n保证是有效的 提示:双指针 注意:是倒数第n个节点 进阶:使用一趟遍历扫描实现 示例 ...
  • 题目: 思路: 代码 方法一:l+1-n 求出链表长度 class Solution { public ListNode ... //倒数第n个节点是正数第l-n个节点 现在有l+1-n个节点 //我们要找到删除的上一个节点 l-n+1 -1 ListNode cur=dum
  • 删除链表第n个节点 给定一个链表删除链表的倒数第n个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3-&...
  • 第一种方法是先循环一遍链表确定结点数n,则倒数第k结点就是就是正数的第n+1-k,然后在遍历一次链表就可以找到指定结点了,但显然需要遍历两遍链表。 第二种方法可以使用两指针,第一指针先走k-1步,然后...
  • leetcode 19 删除链表倒数第N个节点 一次遍历: 设置头结点hh,指向head 双指针pre,cur pre往前移动n个 之后pre和cur共同往前移动,直到pre的next为NULL 返回头指针一定是hh的next(考虑到可能删除的是head) /** ...
  • 19.删除链表倒数第N个节点Java 题目描述 给你一个链表删除链表的倒数第 n 个结点,并且返回链表的头结点。 进阶:你能尝试使用一趟扫描实现吗? 输入输出样式 示例1: 输入:head = [1,2,3,4,5], n = 2 输出:[1,2...
  • 我们可以先将链表反转,这样一来题目就等于变成了删除正数第N个节点,那我们就可以直接遍历到第N个节点,然后原地删除,最后只需要再将链表反转回来即可。 public class Code_19 { public static void main(String...
  • 给定一个链表删除链表的倒数 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数个节点后,链表变为 1->2->3->5. 说明: 给定的 n ...
  • 给定一个链表删除链表的倒数第n个节点并返回链表的头指针 例如, 给出的链表为:1->2->3->4->5, n= 2. 删除链表的倒数第n个节点之后,链表变为1->2->3->5. 备注: 题目保证n一定是有效的 ...
  • 01、哨兵节点链表的题目中,十道有九道会用到哨兵节点,所以我们...举例子,比如我们要删除链表元素,常见的删除链表的操作是找到要删元素的前一元素,假如我们记为 pre。我们通过: pre.Next = pr
  • ##力扣刷题之删除链表倒数第n个节点 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5. 说明: 给定的 n 保证是有效的。 进阶: 你能尝试使用一...
  • 思路:快慢指针,快指针先走n步,然后快慢一起走,直到快指针走到最后,要注意的是可能是要删除第个节点,这个时候可以直接返回head -> next talk is cheap,show me the code! 代码如下: ListNode*

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,558
精华内容 1,423
关键字:

链表删除第n个节点