精华内容
下载资源
问答
  • 删除单链表中第i个节点

    千次阅读 2019-01-06 17:53:14
    单链表删除操作是将单链表第i个节点删去。具体步骤如下:  (1)找到节点ai-1的存储位置p,因为在单链表中节点ai的存储地址是在其直接前趋节点ai-1的指针域next;  (2)令p->next指向ai的直接后继...

    单链表的删除操作是将单链表的第i个节点删去。具体步骤如下: 
    (1)找到节点ai-1的存储位置p,因为在单链表中节点ai的存储地址是在其直接前趋节点ai-1的指针域next中; 
    (2)令p->next指向ai的直接后继节点ai+1; 
    (3)释放节点ai的空间; 

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node
    {
        int data;
        struct node *next;
    } NODE;
    
    
    // 尾插法创建单链表(带头节点)
    NODE *createEnd(int arr[], int len)
    {
        NODE *head = (NODE *)malloc(sizeof(NODE)); // 生成头节点
        head->next = NULL;
        NODE *end = head;  // 尾指针初始化
    
        for (int i = 0; i < len; i++) {
    
            NODE *p = (NODE *)malloc(sizeof(NODE)); // 为每个数组元素建立一个节点
            p->data = arr[i];
            end->next = p;  // 将节点p插入到终端节点之后
            end = p;
        }
    
        end->next = NULL;  // 单链表建立完毕,将终端节点的指针域置空
    
        return head;
    }
    
    
    // 删除单链表中第i个节点
    NODE *delete(NODE *head, int i)
    {
        NODE *p = head;
    
        int j = 1;
        while (p->next && j < i) {
            p = p->next;
            ++j;
        }
    
        if (p->next == NULL || j > i) { // 经过循环,若最终p为空,或i为0或负数时,都说明位置不合理;
            printf("Position Error\n");
            return 0;
        }
    
    
        NODE *temp = p->next;
        p->next = temp->next;
    
        free(p);
    
        return head;
    }
    // 注: (1)设单链表的长度为n,则单链表删除第i个节点时,必须保证 1<= i <= n,否则不合法;
    //     (2)当 i=n+1 时,虽然被删除节点不存在,但其前趋节点却存在,它是终端节点;所以,被删节点的直接前趋*p存在,并不意味着被删节点就一定存在,仅当*p存在(即p != NULL)且*p不是终端节点(即p->next != NULL)同时满足 j <= i时,才能确定被删节点存在。此时,算法的时间复杂度是O(n)。
    
    
    // 单链表打印
    void print(NODE *head)
    {
        if (head == NULL) return;
    
        NODE *p = head->next;
        while (p != NULL) {
            printf("%d\n", p->data);
            p = p->next;
        }
    }
    
    int main(void)
    {
        int arr[] = {1,2,3,4,5,6,7};
        int len = sizeof(arr)/sizeof(int);
    
        NODE *head = createEnd(arr, len);
    
        // 删除前
        print(head);
    
    
        delete(head, 5);
        // 删除后
        print(head);
    
        return 0;
    }
    

     

    展开全文
  • 如何删除单链表中第i个节点? 先来看看删除的原理:因为数据结构是单链表,要想删除i个节点,就要找到第i个节点;要想找到第i个节点,就要找到第i-1个节点;要想找到第i-1个节点,就要找到第i-2个节点......于是...

    如何删除单链表中第i个节点?

    先来看看删除的原理:因为数据结构是单链表,要想删除第i个节点,就要找到第i个节点;要想找到第i个节点,就要找到第i-1个节点;要想找到第i-1个节点,就要找到第i-2个节点......于是就要从第一个节点开始找起,一直找到第i-1个节点。如何找?让一个指针从头结点开始移动,一直移动到第i-1个节点为止。这个过程中可以用一个变量j从0开始计数,一直自增到i-1。


    之后呢?我们把第i-1个节点找到了,就让它的指针域指向第i+1个节点,这样就达到了删除的目的。而第i+1个节点的地址又从第i个节点获得,第i个节点的地址又是第i-1个节点的后继。因此我们可以这样做:先让一个指针指向第i-1个节点的后继,(保存i+1节点的地址),再让i-1节点的后继指向第i个节点的后继,这样就将第i个节点删除了。

    再来看看删除的时候会遇到什么意外情况:
    1.有可能单链表一开始就为空。这样的话连第i-1个元素都找不到。


    2.有可能找不到第i个节点,原因是第i-1的后继为空。

    3.有可能删除的位置不合理,比如删除第-1个节点。



    如何删除单链表中数据域为x的前驱节点?

    这个删除操作其实和上面的类似。关键是要知道三个地址,p->第i-2个节点的地址,q->第i-1个节点的地址,r->元素为x的第i个节点的地址。(为什么?因为我们要删除的是第i-1个节点。要想删除它,就既要找到第i-2个节点,又要找到元素为x的第i个节点)


    假设三个指针,p,q,r。p=L(L为头结点的地址)。q=p->next;(这里要注意先判断q是否为空?如果q为空,意味着L->next为空。空链表,不予受理!!!!!!) r=q->next;(这样子,三个指针就连续了)

    当r->data!=X,并且r!=null时(最前面的指针指向的节点数据域不是x,并且这个指针有节点去指向)
    让指针移动,p=q;q=r;r=r->next;这样就找到了满足条件的三个地址。


    找到了地址,下一步是删除。要注意的一点是,什么时候可以删除?只有当r!=null,才能删。否则不满足题目一开始的条件了。
    删除操作:p->next=q->next;free(q);
    展开全文
  • 删除单链表倒数n个节点

    千次阅读 2016-10-12 21:28:10
    如何删除单链表中的倒数n个节点? 使用快慢指针法,实现一次遍历进行删除

    基本问题

    如何删除单链表中的倒数第n个节点?

    常规解法

    先遍历一遍单链表,计算出单链表的长度,然后,从单链表头部删除指定的节点。

    代码实现

     /**
      * 
      * Description: 删除单链表倒数第n个节点,常规解法.
      *
      *  @param  head
      *  @param  n
      *  @return  ListNode
      */
     public   static  ListNode removeNthFromEnd(ListNode head,  int  n) {
         if  (head ==  null )
             return   null ;
         //get length of list
        ListNode p = head;
         int  len = 0;
         while  (p !=  null ) {
            len++;
            p = p. next ;
        }
         //if remove first node
         int  fromStart = len - n + 1;
         if  (fromStart == 1)
             return  head. next ;
         //remove non-first node    
        p = head;
         int  i = 0;
         while  (p !=  null ) {
            i++;
             if  (i == fromStart - 1) {
                p. next  = p. next . next ;
            }
            p = p. next ;
        }
         return  head;
    }

    一次遍历法

    使用快慢指针。快指针比慢指针提前n个单元。当快指针到达单链表尾部时,慢指针指向待删除节点的前节点。

    代码实现

     /**
      * 
      * Description: 删除单链表倒数第n个节点,快慢指针法.
      *
      *  @param  head
      *  @param  n
      *  @return  ListNode
      */
     public   static  ListNode removeNthFromEnd(ListNode head,  int  n) {
         if  (head ==  null )
             return   null ;
        ListNode fast = head;
        ListNode slow = head;
         for  ( int  i = 0; i < n; i++) {
            fast = fast. next ;
        }
         //if remove the first node
         if  (fast ==  null ) {
            head = head. next ;
             return  head;
        }
         while  (fast. next  !=  null ) {
            fast = fast. next ;
            slow = slow. next ;
        }
        slow. next  = slow. next . next ;
         return  head;
    }
    展开全文
  • 删除单链表倒数k个节点,要求时间复杂度为n,空间复杂度为1。 解题方法1 最简单的方法,先将链表遍历一遍求出链表长度n,那么倒数k个节点其实就是n-k+1个节点。 然后再次遍历链表找到待删除节点删除节点...

    题目描述

    • 删除单链表倒数第k个节点,要求时间复杂度为n,空间复杂度为1。

    解题方法1

    • 最简单的方法,先将链表遍历一遍求出链表长度n,那么倒数第k个节点其实就是第n-k+1个节点。
    • 然后再次遍历链表找到待删除的节点和删除节点前一个节点即可。
    public class Test {
        public static void main(String[] args) throws Exception {
             int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12};
             Node head = create1(arr);
            delnode(head,10);
             for(Node p=head.next;p!=null;p=p.next){
                 System.out.print(p.val + " ");
             }
        }
        //删除倒数第k个节点
        public static void delnode(Node head,int k){
            int len=0;
            for(Node p=head.next;p!=null;p=p.next){
                len++;
            }
            int num = len-k+1;
            if(num>len || num<1){
                return;
            }
            //找到第num-1个节点
            Node prenode = head;
            for(int i=0;i<num-1;i++){
                prenode = prenode.next;
            }
            //删除第num个节点
            prenode.next = prenode.next.next;
        }
        //创建一个单链表
        public static Node create1(int[] arr){
            Node head = new Node(0); //头节点
            Node newnode = null; //指向新节点
            Node lastnode = head; //指向链表尾节点
            for(int a:arr){
                newnode = new Node(a); //创建新节点
                newnode.next = lastnode.next; //尾插核心操作
                lastnode.next = newnode;
                lastnode = newnode; //迭代指针
            }
            return head;
        }
    }
    class Node{
        int val;
        Node next;
        Node(int val){
            this.val = val;
        }
    }
    
    展开全文
  • 单链表倒数K值 题目: 找出单链表的倒数K元素,比如给定单链表:1->2->3->...1、单链表中的每个节点包含数据和指向下一个节点的指针 public class LNode { int data; //数据域...
  • #include <stdio.h>...//数组 构建成单链表 (带头结点) struct LNode* creat(int a[],int n) { LNode* head=(LNode*)malloc(sizeof(LNode)); LNode* p=head; for(int i=0;i<n;i++) {
  • 难度:两星 如何删除单链表得倒数N个节点?这里依然利用快慢指针的办法,让slow指针指向一...这里找到了N个节点之后需要删除掉这个节点,那么因为是单链表,我们必须保留被删除节点之前的这个节点,以及被删...
  • 单链表 之 将该单链表中第i个位置的结点插入到第j位置的节点之前,保持其他结点顺序不变 1、题目: 将该单链表中第i个位置的结点插入到第j位置的节点之前,保持其他结点顺序不变。 输入:链表头结点,i,j ...
  • 单链表主类 参考单链表反转的主类代码 ...删除操作需要拿到倒数lastNum+1个节点来完成,即正数size-lastNum个节点,index=size-lastNum-1 把该节点的next设置为该节点的next.next即可 代码 public...
  • 删除单链表中倒数K个节点

    千次阅读 2019-03-06 20:40:16
    首先设置两个节点 p1 ,p2 都指向head节点,然后先让p2向后移动,直到p1和p2的间隔恰好为K的时候,p1和p2一起向后移动,直到p2.next == null 的时候 那么p1所指的结点就是要删除的结点。 public class ...
  • 本文实例为大家分享了python实现单链表中删除倒数K个节点的具体代码,供大家参考,具体内容如下题目:给定一链表,删除其中倒数k个节点。代码:class LinkedListAlgorithms(object):def __init__(self):pass...
  • 2.满足上面条件后,定义ListNode P=head,重头开始遍历链表,走k步后,退出循环(在此循环,如果没到k,p就为null了,说明没有倒数K个节点,k大于表长度了,直接返回head)。3.定义ListNod...
  • 删除单链表中的重复节点

    千次阅读 2020-06-21 21:59:01
    删除单链表中的重复节点 一、题目描述 已知单链表L,写一算法,删除其中的重复节点。 二、分析解答 2.1 知识点分析 本题主要考察链表的相关知识点,其中包括:单链表的结构、创建、遍历、删除等操作。要想...
  • 删除单链表第i个位置的结点

    千次阅读 2016-08-23 14:52:22
    删除单链表第i个位置的结点,首先需要判断是不是空链表,其次判断删除位置是否合法,最后判断是不是删除第结点,实现过程如下所示: package cn.edu.nwu.structs.linklist; /** * @author jcm * 删除链表...
  • 1)求单链表中有效节点的个数 伪代码(完整代码在下方): 获取头节点: //先初始化一节点,头结点不要动,不存放具体数据 private HeroNode head = new HeroNode(0, "", ""); //获取头节点 public ...
  • 指针指向此单链表中间的一个节点(非个节点, 也非最后一个节点)。请将该节点单链表中删除。解答: 典型的“狸猫换太子”, 若要删除节点,正常情况下,应该要知道该节点的前面节点的指针,但是由于...
  • 指针指向此单链表中间的一个节点(既不是,也不是最后一个节点),请将该节点单链表中删除。 p->data = p->next->data; p->next = p->next->next; firee(p->next);    链表结点定义...
  • 文章目录单向链表1、单链表的 增 删 改 查 思路分析2、代码实现3、练习题# 1求单链表中有效节点个数# 2查找单链表中倒数k个节点# 3单链表的反转# 4从尾到头打印链表# 5合并两个有序链表,合并之后链表依然有序,并...
  • 题目:删除单链表中的重复节点删除重复项;即只要链表某个元素的出现次数大于1,那么就将链表所有的该元素都删除)(即重复的结点不保留) 例如,链表1->3->2->5->6->1->5->7->3->8->2 ,处理后为 6->7->8。 ...
  • 容易 删除链表倒数n个节点 查看运行结果  ...链表节点个数大于等于n 样例 给出链表1->2->3->4->5->null和 n = 2. 删除倒数二个节点之后,这个链表将变成1->2->3->5->null. 挑战
  • 给定一链表,删除链表的倒数n个节点,并且返回链表的头结点。 示例: 给定一链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数个节点后,链表变为 1->2->3->5. 说明: 给定的n...
  • java删除单链表中的重复节点

    千次阅读 2017-09-02 20:24:10
    * 1、删除单链表中的重复节点 * 输入 : 2, 3, 3, 5, 7, 8, 8, 8, 9, 9, 10 * 输出 : 2 5 7 10 * * 2、单链表中重复节点只保留一 * 输入 : 2, 3, 3, 5, 7, 8, 8, 8, 9, 9, 10 * 输出 : 2 3 5 7 8 ...
  • typedef struct Lnode //单链表结构体 { int data; struct Lnode* next; } LinkNode; void DispList(LinkNode*L) //输出函数 { LinkNode*p=L; while(p!=NULL) { printf("%d ",p->data); p=p
  • 来自左神书的一道题,在左神...问题:删除无序单链表中重复出现的节点 思路:使用HashSet进行重复判断。 核心算法: public static void removeNode(Node head){ if(head == null){ return; } HashSet s

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,478
精华内容 12,591
关键字:

删除单链表中第i个节点