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

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

    示例:

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

    说明:

    给定的 n 保证是有效的。

    进阶:

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

     

    思路很简单,采用双指针pre 和index,开始时两个都指向头部。删除倒数第几个就让index指针先走几步。

    然后两个指针同步下移,index的next为空时结束遍历,pre指向的节点就是需要删除的。

    因为pre指向尾节点的情况下不会删除pre指向的节点,所以又加了第三个指针,pre的前指针。

    总的来说这个题目还是偏简单,就是具体实现的时候删除指定节点遇到了点问题,做个记录。

     

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (null == head) {
            return null;
        }
        if (n <= 0) {
            return head;
        }
    
        ListNode exPre = head;
        ListNode pre = head;
        ListNode index = head;
    
        for (int i = 1; i < n; i++) {
            index = index.next;
            if (null == index) {
                return head;
            }
        }
    
        while (index.next != null) {
            exPre = pre;
            pre = pre.next;
            index = index.next;
        }
    
        //pre指向的节点为要删除的节点
        //删除的时候分了两种情况,一种是要删除的节点有后继节点
        if(null != pre.next){
            pre.val = pre.next.val;
            pre.next = pre.next.next;
        }else {
            //要删除的节点没有后继节点。这里又有一个特殊情况就是链表只有一个节点
            if(exPre.next == null){
                return null;
            }
            exPre.next = null;
        }
    
        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个节点,所以我们设置两个快慢指针 tail 和 head,同时对链表进行遍历,并且 tail 比 head 超前 n 个节点。当 tail 遍历到链表的末尾时,head 就恰好处于倒数第 n 个节点。

           public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode tail=head;  //快指针
            ListNode root=head;  //慢指针
    
            int pace; 
    
            for (pace=0;pace<n&&tail!=null;pace++)
                tail=tail.next;
    
            if (pace<n) return null; //若当前链表长度不满足要求,即所给n无效时,返回null
    
            if (tail==null)          //当头节点为倒数第n个节点
                return root.next;
    
            while (tail.next!=null){
                tail=tail.next;
                head=head.next;
            }
            head.next=head.next.next;
    
            return root;
        }
    

    时间复杂度:O(N) 其中 N是链表的长度。

    空间复杂度:O(1)

    展开全文
  • 删除链表倒数第N个节点 删除链表中的节点 题目描述: 237.删除链表中的节点 请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除节点。 现有一个链表 -- head = [4,5,1,9],...

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

    删除链表中的节点

    题目描述:

    237.删除链表中的节点
    请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。
    
    现有一个链表 -- head = [4,5,1,9],它可以表示为:
    4->5->1->9
    
    示例 1:
    
    输入: head = [4,5,1,9], node = 5
    输出: [4,1,9]
    解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.
    示例 2:
    
    输入: head = [4,5,1,9], node = 1
    输出: [4,5,9]
    解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.
     
    
    说明:
    
    链表至少包含两个节点。
    链表中所有节点的值都是唯一的。
    给定的节点为非末尾节点并且一定是链表中的一个有效节点。
    不要从你的函数中返回任何结果。
    

    问题分析:

    利用要删除节点与下一个结点的值的交换,再进行next的变换,完成狸猫换太子的行为,哈哈。
    

    代码展示(已验证):

    //237.删除链表中的节点
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public void deleteNode(ListNode node) {
            node.val = node.next.val;
            node.next = node.next.next;//借助值的转换和next指针指向的不同,完成删除这一结点效果
    
        }
    }
    

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

    题目描述:

    leetcode 19.删除链表的倒数第N个节点
    给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
    
    示例:
    
    给定一个链表: 1->2->3->4->5, 和 n = 2.
    
    当删除了倒数第二个节点后,链表变为 1->2->3->5.
    说明:
    
    给定的 n 保证是有效的。
    
    进阶:
    
    你能尝试使用一趟扫描实现吗?
    
    //链表的创建和打印
    class ListNode{
        int val;
        ListNode next;
        ListNode(int x)
        {
            val = x;
        };
    
        //在链表的尾部添加新的结点
        public void add(int newval){
            ListNode newNode = new ListNode(newval);
    
            if(this.next == null)
                this.next = newNode;
            else
                this.next.add(newval);
        }
        //打印链表
        public void print(){
            System.out.print(this.val);
            if(this.next != null)
            {
                System.out.print("-->");
                this.next.print();
            }
        }
    }
    
    */
    

    问题分析:

    	利用三指针,生成一个下一个结点指向head结点的指针current,再生成一个指向head结点的指针fast,
    先用fast指针走n步,然后使得另一个指针 slow = current,
    和原来的快指针一起移动,当快指针为null时说明慢指针即为要删除的结点
    然后通过赋值给他下一个结点然后,使得next的指向越过一位,就能完成删除
    
    return 的时候返回 current.next
    
    创建一个current指针,来带领链表,使用三个指针可以避免因为长度而导致链表
    过界的问题
    

    代码展示(已验证):

    //leetcode 19.删除链表的倒数第N个节点
    /**
     * 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) {
            if(head.next == null)
                return null;
                
            ListNode fast = head;//定义快指针
    
    		//为链表创建一个新的头,return current.next 来带领整个链表
            ListNode current = new ListNode(-1); 
            current.next = head;
            ListNode slow = current;    //定义慢指针
    
            n = n-1;
            while (n>0 && fast.next!=null)//设置快慢指针的初始位置
            {
                fast = fast.next;
                n--;
            }
            //同时移动,找到要删除的结点
            while(fast.next!=null)
            {
                fast = fast.next;
                slow = slow.next;
            }
            
            //找到要删除的结点后,进行删除操作,不能越界
            slow.next = slow.next.next;
    
            return current.next;
        }
    }
    

    泡泡:
    java中链表的创建和使用
    删除排序链表中的重复元素 I
    删除排序链表中的重复元素 II

    链表这个数据结构,总共两个要义:val,next
    
    设置下一个节点指向头节点的结点
    	ListNode current = new ListNode(-1); 
        current.next = head;
        
    返回上述的链表
    	return current.next;
    	
    设置该节点指向头节点
    	ListNode fast = head;
    	
    节点的移动
    	fast = fast.next;
    	
    节点的删除--指针跨越
    	node.val = node.next.val;
        node.next = node.next.next;
    
    展开全文
  • Java删除链表倒数第K个节点 /** * 删除链表倒数第k个节点 * @param k 倒数第k个节点 * @param head 链表的头结点 * @return 新的头结点 */ public static Node removeLastKthNode(int k, Node head){ if...

    Java删除链表中倒数第K个节点

        /**
         * 删除链表中倒数第k个节点
         * @param k 倒数第k个节点
         * @param head 链表的头结点
         * @return 新的头结点
         */
        public static Node removeLastKthNode(int k, Node head){
            if (head == null || k < 1){
                return head;
            }
            //声明int num用于表示链表的长度
            int num = 0;
            Node temp = head;
            while (temp != null){
                num++;
                temp = temp.next;
            }
            //第一种情况:不存在倒数第k个节点,即k可能超过链表的长度
            if (k > num){
                return head;
            }
            //第二种情况:k可能是头结点
            else if (num == k){
                return head.next;
            }
            //第三种情况:k可能是在第一个节点之后
            else {
                temp = head;
                //等效为删除(num - k + 1)个节点
                while (num - k != 1){
                    temp = temp.next;
                    num--;
                }
                temp.next = temp.next.next;
            }
            return head;
        }
    
    展开全文
  • 主要介绍了Java输出链表倒数第k个节点的相关内容,涉及三种设计思路及代码示例,具有一定参考价值,需要的朋友可以了解下。
  • 删除链表倒数第N个节点java实现) 题目 给定一个链表删除链表倒数第 n 个节点并返回头结点。 例如,给定一个链表: 1->2->3->4->5, 并且 n = 2. 当删除倒数第二个节点链表变成了 1->2->...
  • 删除链表倒数第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...
  • 题目描述:给出一个单链表,返回删除单链表的倒数第 K 个节点链表。 题目链接:https://www.nowcoder.com/questionTerminal/e5d90aac4c8b4628aa70d9b6597c0560 import java.io.BufferedReader; import java.io....
  • 给定一个链表删除链表倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除倒数第二个节点后,链表变为 1->2->3->5. 说明: 给定的...
  • 给定一个链表删除链表倒数第n个节点并返回链表的头指针 例如, 给出的链表为:1->2->3->4->5, n= 2. 删除链表倒数第n个节点之后,链表变为1->2->3->5. 备注: 题目保证n一定是有效的 ...
  • 1、计算出整个链表长度,如果链表长度等于k,直接返回head.next; 2、双指针 fast 和 slow 让fast先走k-1步,为了让下一步遍历结束后slow正好再被删结点的前一个位置,需要让fast再走一步,。 3、两个指针同时开始...
  • 哨兵节点删除链表倒数第N个节点

    千次阅读 2020-09-03 20:56:41
    01、哨兵节点链表的题目中,十道有九道会用到哨兵节点,所以我们...举个例子,比如我们要删除链表的第一个元素,常见的删除链表的操作是找到要删元素的前一个元素,假如我们记为 pre。我们通过: pre.Next = pr
  • 给定一个链表删除链表倒数第 nnn 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除倒数第二个节点后,链表变为 1->2->3->5. 双指针,一遍遍历 ...
  • 给出一个单向链表,删除链表倒数第n个节点,并返回头节点。 例如: 给出链表 1-&amp;gt;2-&amp;gt;3-&amp;gt;4-&amp;gt;5,n=2 返回链表 1-&amp;gt;2-&amp;gt;3-&amp;gt;5 解题...
  • 看到此题,立马想到了找到链表倒数第k个结点 方法类似, 若要删除一个结点,可以将此结点的前驱的后继变成要删除的结点的后继,这样描述可能有点绕,直接看代码:slow.next = slow.next.next,可以理解为跳过要删除...
  • Java实现 LeetCode 19删除链表倒数第N个节点

    万次阅读 多人点赞 2020-02-12 15:09:52
    19. 删除链表倒数第N个节点 给定一个链表删除链表倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除倒数第二个节点后,链表变为 1->2->3-&...
  • 链表,删除链表倒数第N个节点 1. 题目描述 难易度:中等 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后...
  • 输入一个链表,输出该链表倒数第k个结点。 思路: 先定义两个指针,快引用 fast 和慢引用 slow,让 fast 先走 k-1 步,当 fast.next 为空的时候 slow 就是倒数第 k 个节点 看图说明一下 /* public class...
  • 链表倒数第k个节点是一样的。都可以用单指针两次遍历或者双指针一次遍历解决。 2、代码实现 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = ...
  • 1.首先让快指针走K步,如果fast==null(K等于链表的长度),说明要删除的为链表第1个节点,直接返回head.next 2.然后让快慢指针一起走,直到走到链表结束,此时慢指针在倒数第K+1个节点,直接执行slow.next=slow....
  • 19. 删除链表倒数第N个节点 给定一个链表删除链表倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除倒数第二个节点后,链表变为 1->2->3-...
  • 文章目录一、题目描述...给定一个链表删除链表倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除倒数第二个节点后,链表变为 1->2->3-&g...
  • 给定一个链表删除链表倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除倒数第二个节点后,链表变为 1->2->3->5. 说明: 给定的 n 保证是...
  • 输入一个链表,输出该链表倒数第k个结点。 2. 解体思路 方法一:简单来说就是先遍历整个链表的长度L,然后根据k,从头节点开始遍历,到L-k,得到相应的节点。 方法二:两个指针,先让第一个指针和第二个指针都指向...
  • Java实现Leetcode链表-删除链表倒数第N个节点 一、 问题描述 给定一个链表删除链表倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除倒数第二个...
  • 给定一个链表删除链表倒数第n个节点,并且返回链表的头结点。 示例 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除倒数第二个节点后,链表变为 1->2->3->5. 思路与代码 ​...
  • 删除链表中的倒数第n个节点

    千次阅读 2018-11-18 11:08:42
    给定一个链表删除链表倒数第n个节点,并且返回链表的头结点。 示例: 给定一个链表: 1-&gt;2-&gt;3-&gt;4-&gt;5, 和 n = 2. 当删除倒数第二个节点后,链表变为 1-&gt;2-&gt;3-&...
  • 19.删除链表倒数第N个节点Java 题目描述 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 进阶:你能尝试使用一趟扫描实现吗? 输入输出样式 示例1: 输入:head = [1,2,3,4,5], n = 2 输出:[1,2...
  • 给定一个链表删除链表倒数第n个节点,返回链表的头节点。  注意事项 链表中的节点个数大于等于n 您在真实的面试中是否遇到过这个题?  Yes 样例 给出链表1->2->3->4-...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,292
精华内容 4,516
关键字:

java删除链表倒数节点

java 订阅