精华内容
下载资源
问答
  • 删除链表的倒数第N个节点 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点
    2020-04-18 00:56:03

    一、思路:

         遍历一遍存储节点到vector数组中,然后利用数组指向倒数第n个,将倒数n-1的节点的next指向倒数n的next

    二、代码:

    class Solution {
    public:
    	ListNode* removeNthFromEnd(ListNode* head, int n) {
    		vector<ListNode*>nodeLists;
    		ListNode *nowNode = head;
    		while (nowNode != NULL) {
    			nodeLists.push_back(nowNode);
    			nowNode = nowNode->next;
    		}
    		int index = nodeLists.size() - n;
    		if (index <= 0)
    			return head->next;
    		nodeLists[index - 1]->next = nodeLists[index]->next;
    		delete nodeLists[index];
    		return head;
    	}
    };
    

     

    更多相关内容
  • 给定一个链表,删除链表的倒数第 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 保证是有效的。 进阶: 你能...
  • 实现删除链表倒数第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 保证是有效的。

    思路:使用两个结点,一个是p,一个是q。先让p向前走n步,然后p和q同时向前走,当p走到头的时候,q即是倒数n+1个结点了。另q.next=q.next.next,则删除了倒数第n个结点。

    有两种特殊情况:

    1.链表长度小于n,则返回原链表

    2.链表长度为n,则返回head.next

    代码实现:

    /**

    * 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 p = head;

    int i;

    for(i = 0; i < n; i++) //用于判断链表长度,同时让p先走n步

    {

    p = p.next;

    if(p == null)

    break;

    }

    if(i == n - 1 && p ==null) //链表长度为n时,头结点就是倒数第n个结点,删除头结点即可

    return head.next;

    if(i < n - 1 && p == null) //如果链表长度小于n,则不需要删除结点,返回原链表即可

    return head;

    ListNode q = head;

    while(p.next != null)

    {

    //这时让p和q同时向前走,直到链表遍历完成

    p = p.next;

    q = q.next;

    }

    q.next = q.next.next;

    return head;

    }

    }

    展开全文
  • 主要介绍了python实现获取单向链表倒数第k个结点的值,结合实例形式分析了Python针对单向链表的定义、遍历、传值、判断等相关操作技巧,需要的朋友可以参考下
  • 哨兵节点:删除链表倒数第N个节点

    千次阅读 2020-09-03 20:56:41
    哨兵节点,其实就是一附加在原链表最前面用来简化边界条件的附加节点,它的值域不存储任何东西,只是为了操作方便而引入。 比如原链表为a->b->c,则加了哨兵节点链表即为x->a->b>c,如下图: 那...

    01、哨兵节点

    在链表的题目中,十道有九道会用到哨兵节点,所以我们先讲一下什么是哨兵节点。

    哨兵节点,其实就是一个附加在原链表最前面用来简化边界条件的附加节点,它的值域不存储任何东西,只是为了操作方便而引入。

    比如原链表为a->b->c,则加了哨兵节点的链表即为x->a->b>c,如下图:

    在这里插入图片描述

    那我们为什么需要引入哨兵节点呢?举个例子,比如我们要删除某链表的第一个元素,常见的删除链表的操作是找到要删元素的前一个元素,假如我们记为 pre。我们通过:

    pre.Next = pre.Next.Next

    来进行删除链表的操作。但是此时若是删除第一个元素的话,你就很难进行了,因为按道理来讲,此时第一个元素的前一个元素就是nil(空的),如果使用pre就会报错。那如果此时你设置了哨兵节点的话,此时的pre就是哨兵节点了。这样对于链表中的任何一个元素,你要删除都可以通过pre.Next=pre.Next.Next的方式来进行,这就是哨兵节点的作用。

    下面我们看一道题目,看一下哨兵节点的应用

    02、题目讲解

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

    示例:

    给定一个链表: 1->2->3->4->5, 和 n = 2.
    当删除了倒数第二个节点后,链表变为 1->2->3->5.
    

    说明:

    • 给定的 n 保证是有效的。

    进阶:

    • 你能尝试使用一趟扫描实现吗?

    思路分析:

    首先我们思考,让我们删除倒数第N个元素,那我们只要找到倒数第N个元素就可以了,那怎么找呢?我们**只需要设置两个指针变量,中间间隔N-1元素。当后面的指针遍历完所有元素指向nil时,前面的指针就指向了我们要删除的元素。**如下图所示:

    在这里插入图片描述

    接下来,我们只要同时定位到要删除的元素的前1个元素,通过前面讲过的删除操作,就可以很顺利的完成这道题目啦。

    03、解题过程

    现在我们来完整捋一遍解题过程:

    1. 首先我们定义好哨兵节点result,指向哨兵节点的目标元素指针cur,以及目标指针cur的前一个指针pre,此时pre指向nil。
    2. 接下来我们开始遍历整个链表。
    3. 当head移动到距离目标元素cur的距离为N-1时,同时开始移动cur。
    4. 当链表遍历完之后,此时head指向nil,这时的cur就是我们要找的待删除的目标元素。
    5. 最后我们通过pre.Next = pre.Next.Next完成删除操作,就完成了整个解题过程。

    下面是解题过程图,可以看得更清楚哦。

    在这里插入图片描述

    04、题目解答

    根据以上分析,我们可以得到下面的题解:

    func removeNthFromEnd(head *ListNode, n int) *ListNode {
        result := &ListNode{}
        result.Next = head
        var pre *ListNode
        cur := result
        i := 1
        for head != nil {
            if i >= n {
                pre = cur
                cur = cur.Next
            }
            head = head.Next
            i++
        }
        pre.Next = pre.Next.Next
        return result.Next
    }
    

    再给个java版:

    class Solution {
     
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode result = new ListNode(0);
            result.next = head;
            ListNode pre = null;
            ListNode cur = result;
            int i = 1;
            while (head != null) {
                if (i >= n) {
                    pre = cur;
                    cur = cur.next;
                }
                head = head.next;
                i ++;
            }
            
            pre.next = pre.next.next;
    
            return result.next;
        }
    
    }
    

    我把我写的所有题解都整理成了一本电子书,每道题都配有完整图解。点击即可下载

    和小浩学算法

    展开全文
  • 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点
    在本题中,如果我们要删除节点 yy,我们需要知道节点 yy 的前驱节点 xx,并将 xx 的指针指向 yy 的后继节点。
    但由于头节点不存在前驱节点,因此我们需要在删除头节点时进行特殊判断。
    但如果我们添加了哑节点,那么头节点的前驱节点就是哑节点本身,此时我们就只需要考虑通用的情况即可。
    public class DeleteNthDesc {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummy = new ListNode(0, head); //定义虚拟头头节点
            int length = getLength(head); //获取head链表的大小
            ListNode cur = dummy;
            //获取被删除节点的上一个节点【因为是删除倒数的节点,又因为是链表,所以我们必须从正面来】
            for (int i = 1; i < length - n + 1; ++i) {
                cur = cur.next;
            }
            cur.next = cur.next.next; //删除节点
            ListNode ans = dummy.next; //返回删除后的头结点链表
            return ans;
        }
        //获取链表大小
        public int getLength(ListNode head) {
            int length = 0;
            while (head != null) {
                ++length;
                head = head.next;
            }
            return length;
        }
    }
    
    
    class ListNode {
        int val;
        ListNode next;
    
        ListNode() {
        }
    
        ListNode(int val) {
            this.val = val;
        }
    
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    展开全文
  • 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点
  • 图解:删除链表倒数第N个节点

    千次阅读 2020-09-02 23:01:24
    给定一个链表,删除链表倒数第n个节点,并且返回链表的头结点。 示例: 给定一个链表:1->2->3->4->5,和 n = 2。当删除了倒数第二个节点后,链表变为 1->2->3->5。 说明: 给定的n保证是...
  • 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 示例 1: 输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 示例 2: 输入:head = [1], n = 1 输出:[] 示例 3: 输入:head = [1,2], n = 1...
  • 本题是LeetCode第19题,以后题目也可能会变。...思路:用两个节点,删除让前一个节点比后一个节点先跑n次,然后两一起跑。当前一个节点遍历结束或者为空的时候,后一个节点是要删除的元素,但是要删除...
  • ————— 第二天 —————什么意思呢?我们以下面这个链表为例:给定链表的头结点,但并不知道链表的实际长度,要求我们找到链表的倒数第n个结点。假设n=3,那么要寻找的结点就是元素1...
  • | 删除链表中倒数第N个节点 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 示例 2: 输入:head = [1], n = 1 输出:[] 示例 3: 输入:...
  • 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5. 说明: 给定的 n ...
  • 尾插法(用尾插法建立链表);2.头插法(用头插法建立链表);3.显示(打印链表);4.求表长(输出链表长度);5.后插(在指定节点后面插入);6.前插(在指定节点前面插入);7.按位置插入(将元素插入指定位置);...
  • 要求:给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 解法:设置双指针,如果要删除第n个节点,就让一指针比另外一指针快n步 /** * ...
  • 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 示例 1: 输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 示例 2: 输入:head = [1], n = 1 输出:[] 示例 3: 输入:head = [1,2], n ...
  • 删除链表的倒数第N个节点 删除链表中的节点 题目描述: 237.删除链表中的节点 请编写一函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。 现有一个链表 -- head = [4,5,1,9],...
  • Javascript(JS)实现力扣Leecode 19. 删除链表的倒数第 N 个结点
  • 问题描述:给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。示例:给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后,链表变为 1->2->3->5.解题思路:采用...
  • 给定一个链表,删除链表的倒数第n个节点并返回链表的头指针 public ListNode removeNthFromEnd (ListNode head, int n) { //如果n小于等于0直接输出头结点吧 if(n<=0){ return head; } //接下来的n全都...
  • 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5. 说明:给定的 n 保证是...
  • 1.3.2 给定一个链表,删除链表的倒数第N个节点,并且返回链表的头结点
  • 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 LeetCode原题地址:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/ 测试用例 示例 1 输入:head = [1,2,3,4,5], n = 2...
  • 对于除了根结点以外的每点都是有一父亲结点,所以一共有n-1指针指向某个结点,于是形成n-1有内容的链域(减1即是父亲结点)所以一共有2*n-(n-1)=n+1链域没有指向任何东西。 方法2: 二叉树中: 结点数n=n1...
  • 给定链表 head 和两整数 m 和 n. 遍历该链表并按照如下方式删除节点: - 开始时以头节点作为当前节点. - 保留以当前节点开始的前 m 个节点. ...在删除了指定结点之后, 返回修改过后的链表的头节点.
  • 删除链表的倒数第n个节点 题目描述 给定一个链表,删除链表的倒数第n个节点并返回链表的头指针 例如, 给出的链表为:1->2->3->4->5, n= 2. 删除了链表的倒数第n个节点之后,链表变为1->2->3->5....
  • 删除链表的倒数第N个节点(Java)

    千次阅读 2019-02-13 17:54:59
    用一指针来操作head节点,最好不要直接操作head节点。 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 314,525
精华内容 125,810
关键字:

对于n个节点的链表