精华内容
下载资源
问答
  • 之前,小编已经写了如何在单链表中删除一个节点不是数字‘2’ 的代码,那现在改变题目一下,就是如何删除单链表中最后一个节点不是数字‘2’。其实,思路跟删除第一个节点有点相似,就是得用递归来traverse到最后...

    之前,小编已经写了如何在单链表中删除第一个节点不是数字‘2’ 的代码,那现在改变题目一下,就是如何删除单链表中最后一个节点不是数字‘2’。

    其实,思路跟删除第一个节点有点相似,就是得用递归来traverse到最后一个节点,然后进行判断最后一个节点是否是数字‘2’。

    下面是list.h 文件里代码展示

    //list.h
    #include<iostream>
    #include<cstring>
    #include<cctype>
    
    using namespace std;
    
    struct node
    {
        int data;
        node * next;
    };
    
    class list
    {
        public:
            //These function are already written
            list();
            ~list();
            void build();
            void display();
    
            //This is the prototype for this question
            //Remove the last node if the last node is not 2
            void remove_last();
    
        private:
            //Remove the last node if the last node is not 2
            void remove_last(node *& tail, node * head);
    
            node * head;
            node * tail;
    };

    我相信,很多人就会觉得直接用tail指针来判断最后一个节点是否是2,如果不是2,那就直接删除,那tail指针就得指向倒数第二个节点上,不然就会出seg fault,所以就得用head指针来进行traverse到倒数第二个节点上,来进行判断最后一个节点。因为是更改链表,就得pass by reference,不能pass by value,所以在prototype上写的是node *& tail。

    下面是实现这个函数的代码展示:

    //list.cpp
    #include "list.h"
    
    void list::remove_last()
    {
        remove_last(tail,head);
    }
    
    void list::remove_last(node *& tail, node * head)
    {
        if(!head)
            return;
        if(!head->next->next)
        {
            if(head->next->data != 2)
            {
                delete head->next;
                head->next = NULL;
                tail = head;
                return;
            }
            else
                return;
        }
        remove_last(tail,head->next);
    }

    上面就是如何实现这道题的代码,感觉是不是挺简短精辟呢!其实递归就是能使代码量缩小的,而且能让别人很清楚你的思路是什么样的。

    下面是结果展示:
    结果展示

    如果最后一个节点是2的话,就不删除,结果同样展示出来给你们看看:
    结果展示

    是不是感觉很神奇呢,递归就是这么神奇!

    下次,小编还会继续使用递归来实现不同数据结构中的不同功能,敬请期待哦!

    记得为小编点赞哦!!

    展开全文
  • 原文连接:http://www.pixelstech.net/article/1446199844-Algorithm-%3A-Delete-middle-node-from-singly-linked-list点击打开链接 ...假设你知道的唯一信息是一个指向单链表中某一中间节点的指针,关于

    原文连接:http://www.pixelstech.net/article/1446199844-Algorithm-%3A-Delete-middle-node-from-singly-linked-list点击打开链接

    关于单链表的问题在技术面试中被频繁问到,今天我们就将和你分享一个关于单链表的算法问题,以下是问题描述:

    假设你知道的唯一信息是一个指向单链表中某一中间节点的指针,关于这个单链表的其他信息你都不知道,请在不影响单链表结构的前提下删除这个节点。

    一开始可能会认为如果你知道头结点这个问题就很简单,不幸的是我们不知道头结点在哪也因此无法知道这个节点的前驱指针。实际上我们有一个巧妙的方法来“删除”这个指针。我们只需要将这个指针后继节点指向的内容覆盖这个指针就行了,而不是删除它。(这样也就使前驱指针的next指向了要删除节点的next指针指向的节点)

    下面是一个用C语言写的例子:

    #include <stdio.h>
     
    struct Node {
        struct Node* next;
        char value;
    };
     
    // Print the singlely linked list
    void printList(struct Node* head){
        while (head != 0){
            printf("%c->", head->value);
            head = head->next;
        }
        printf("null\n");
    }
     
    // Remove one node from linked list
    void removeNode(struct Node* node){
        if (node->next == 0){
            node->value = '0';
            node = 0;
        }
        else {
            struct Node* next = node->next;
            node->value = next->value;
            node->next = next->next;
            next = 0;
        }
    }
     
    int main(){
        struct Node* a = malloc(sizeof(struct Node));
        struct Node* b = malloc(sizeof(struct Node));
        struct Node* c = malloc(sizeof(struct Node));
        struct Node* d = malloc(sizeof(struct Node));
     
        a->value = 'A';
        b->value = 'B';
        c->value = 'C';
        d->value = 'D';
     
        a->next = b;
        b->next = c;
        c->next = d;
        d->next = 0;
     
        // print the original list
        printList(a);
     
        // remove node c
        removeNode(c);
     
        // print the new list
        printList(a);
     
        free(a);
        free(b);
        free(c);
        free(d);
    }
    输出结果将会是:

    A->B->C->D-null

    A->B->D->null

    展开全文
  • 阅读c-algorithms代码时,又看到如下的代码(删除单链表中任意一个节点) /* A singly-linked list */ struct _SListEntry { SListValue data; SListEntry *next; }; int slist_remove_data(SListEntry **...
    在阅读c-algorithms代码时,又看到如下的代码(删除单链表中任意一个节点)

    /* A singly-linked list */
    
    struct _SListEntry {
         SListValue data;
         SListEntry *next;
    };
    
    int slist_remove_data(SListEntry **list, SListEqualFunc callback, SListValue data)
    {
         SListEntry **rover;
         SListEntry *next;
         int entries_removed;
    
         entries_removed = 0;
    
         /* Iterate over the list.  'rover' points at the entrypoint into the
         * current entry, ie. the list variable for the first entry in the
         * list, or the "next" field of the preceding entry. */
        
         rover = list;
    
         while (*rover != NULL) {
             
              /* Should this entry be removed? */
             
              if (callback((*rover)->data, data) != 0) {               
                   /* Data found, so remove this entry and free */
                   next = (*rover)->next;
                   free(*rover);
                   *rover = next;
                  
                   /* Count the number of entries removed */
                   ++entries_removed;
              } else {               
                   /* Advance to the next entry */
                   rover = &((*rover)->next);
              }
         }
    
         return entries_removed;
    }

    上面的函数实现不仅可以去除头节点,也可以去除中间的任意节点。它依赖的技巧就是节点指针的指针:用节点指针的指针来保存前面一个节点的next域的指针,从而在去除当前节点之前,可以将当前节点的下一个节点link/assign到那个保存的next指针域中。

    我们通常的做法可能会区分对待头节点,并维护一个prev节点指针。

    上面的方法巧妙并且通用的解决了上面的问题。
    找到一张以前画的示意图(跟上面的代码变量定义有些出入):


    展开全文
  • 在单链表中删除指定值的节点 题目 给定一个单链表和一个数val,删除链表中所有值为val的节点。例如: 1->2->3->4,删除3,结果为: 1->2->4 思路1: 用栈 def remove_node_with_val1(head, val): ...

    在单链表中删除指定值的节点

    题目

    给定一个单链表和一个数val,删除链表中所有值为val的节点。例如:
    1->2->3->4,删除3,结果为:
    1->2->4

    思路1: 用栈

    def remove_node_with_val1(head, val):
        stack = []
        p = head
        while p:
            if p.val != val:
                stack.append(p)
            p = p.next
    
        head = None
        while stack:
            p = stack.pop()
            p.next = head
            head = p
    
        return head
    
    

    思路2: 直接操作链表

    def remove_node_with_val2(head, val):
        while head and head.val == val:
            head = head.next
    
        if not head:
            return head
    
        pre = head
        cur = head.next
        while cur:
            if cur.val == val:
                pre.next = cur.next
            else:
                pre = cur
            cur = cur.next
    
        return head
    
    

    测试

    import random
    import operator
    
    
    class Node():
        def __init__(self, val):
            self.val = val
            self.next = None
    
    
    def make_linklist(datas):
        head, tail = None, None
        for d in datas:
            node = Node(d)
            if not head:
                head = node
                tail = node
            else:
                tail.next = node
                tail = node
    
        return head
    
    
    def dump_to_list(head):
        l = []
        p = head
        while p:
            l.append(p.val)
            p = p.next
    
        return l
    
    
    def test(count, maxval, val):
        datas = []
        for _ in range(count):
            d = random.randint(0, maxval)
            datas.append(d)
    
        head = make_linklist(datas)
        l = dump_to_list(head)
        print(l, 'remove', val)
    
        head = remove_node_with_val1(head, val)
        l = dump_to_list(head)
        print(l)
    
        head = make_linklist(datas)
        head = remove_node_with_val2(head, val)
        l = dump_to_list(head)
        print(l)
    
        while val in datas:
            datas.remove(val)
        print(datas)
    
    
    def test1(count, maxval, val):
        datas = []
        for _ in range(count):
            d = random.randint(0, maxval)
            datas.append(d)
    
        head = make_linklist(datas)
        head = remove_node_with_val1(head, val)
        l1 = dump_to_list(head)
    
        head = make_linklist(datas)
        head = remove_node_with_val2(head, val)
        l2 = dump_to_list(head)
    
        while val in datas:
            datas.remove(val)
    
        if not operator.eq(datas, l1):
            raise Exception('Error 1')
    
        if not operator.eq(datas, l2):
            raise Exception('Error 2')
    
    
    if __name__ == '__main__':
        test(10, 5, 2)
        test(10, 2, 2)
        test(20, 10, 2)
        test(20, 15, 2)
        test1(100, 20, 2)
        test1(200, 20, 2)
        test1(2000, 20, 2)
    

    结果

    [3, 5, 2, 4, 0, 1, 2, 2, 5, 5] remove 2
    [3, 5, 4, 0, 1, 5, 5]
    [3, 5, 4, 0, 1, 5, 5]
    [3, 5, 4, 0, 1, 5, 5]
    [1, 1, 0, 2, 0, 1, 0, 1, 1, 2] remove 2
    [1, 1, 0, 0, 1, 0, 1, 1]
    [1, 1, 0, 0, 1, 0, 1, 1]
    [1, 1, 0, 0, 1, 0, 1, 1]
    [7, 8, 2, 7, 3, 3, 1, 0, 3, 8, 8, 9, 0, 8, 4, 5, 9, 1, 0, 1] remove 2
    [7, 8, 7, 3, 3, 1, 0, 3, 8, 8, 9, 0, 8, 4, 5, 9, 1, 0, 1]
    [7, 8, 7, 3, 3, 1, 0, 3, 8, 8, 9, 0, 8, 4, 5, 9, 1, 0, 1]
    [7, 8, 7, 3, 3, 1, 0, 3, 8, 8, 9, 0, 8, 4, 5, 9, 1, 0, 1]
    [9, 6, 11, 0, 10, 15, 14, 9, 2, 11, 8, 4, 0, 8, 8, 12, 13, 6, 7, 7] remove 2
    [9, 6, 11, 0, 10, 15, 14, 9, 11, 8, 4, 0, 8, 8, 12, 13, 6, 7, 7]
    [9, 6, 11, 0, 10, 15, 14, 9, 11, 8, 4, 0, 8, 8, 12, 13, 6, 7, 7]
    [9, 6, 11, 0, 10, 15, 14, 9, 11, 8, 4, 0, 8, 8, 12, 13, 6, 7, 7]
    
    
    展开全文
  • 这个题目我们遇到这个问题的时候可能会想这个该怎么解,我们知道如果一个已知的节点之后添加和删除一个节点的话很容易的,那么如何给定的节点之前插入一个节点以及删除指定节点?因为如果想删除和插入一个节点的...
  • 之前的文章【python单链表中如何插入和输出节点?】中给大家介绍了单链表是什么,以及如何进行添加节点、输出所以节点。下面本篇文章给大家介绍如何查找和删除节点,希望对大家有所帮助。如何从单链表中查找节点?...
  • 这个题目我们遇到这个问题的时候可能会想这个该怎么解,我们知道如果一个已知的节点之后添加和删除一个节点的话很容易的,那么如何给定的节点之前插入一个节点以及删除指定节点?因为如果想删除和插入一个节点的...
  • 删除单链表中在一个范围内的值 typedef struct LNode { ElemType data; LNode *next; }*LinkList; 节点结构体 Status InitList(LinkList &L) //初始化 { L=new LNode; L->next=NULL; return ok; } ...
  • 算法总结之 在单链表中删除指定值的节点 给定一个链表的头节点head和一个整数num,请实现函数将值num的节点全部删除 方法一 利用栈或者其他容器收集的方法 时间复杂度O(N) 额外空间复杂度O(N) ...
  • 实现一个函数,可以删除单链表中倒数第K个节点。 要求 如果链表长度为N,时间复杂度达到O(N),额外空间复杂度达到O(1)。 思路 如果链表为空或者K值小于1,直接返回head即可,除此之外,从头遍历链表,并让K-1. ...
  • 题目: 给定一个链表,删除其中倒数第k个结点。代码:class LinkedListAlgorithms(object): ... pass def rm_last_kth_node(self, k, linked_list): # 删除倒数第 K 个节点,针对单链表的 if linked_list.is_empty
  • 题目:在单链表中删除指定值的节点   方法一:利用一个栈结构。   class Node{ Integer value; public Node next; public Node(Integer data){ this .value = da...
  • 在单链表中删除指定值的节点    给定一个链表的头节点head和一个整数num,实现一个函数删除链表中值为num的所有节点。例如,链表为 1->2->3->4->null ,num 为3,删除后,链表变为 1->2->4->...
  • 给定一个链表的头节点head和一个整数num,请实现函数将值为num的节点全部删除 【代码1】 时间复杂度O(n),空间复杂度O(n) class Solution { public ListNode deleteNode(ListNode head, int val) { ListNode cur =...
  • [注]:如果不是带有节点设置一个虚拟节点即可,返回时返回dummy->next。 struct node { int val; node *next; }; void delInterval(node *head, int minx, int maxx) { if (!head) return head; node *pre =...
  • 算法总结之 删除无序单链表中重复出现的节点 给定一个无序单链表的头节点head,删除其中重复出现的节点 ...2 从头节点的下一个节点开始往后遍历 cur,检查是否哈希表中,删除,...
  • 在单链表中删除倒数第 K 个节点 要求 如果链表的长度为 N, 时间复杂度达到 O(N), 额外空间复杂度达到 O(1) 难度 士 解答 删除的时候会出现三种情况: 1、不存在倒数第 K 个节点,此时不用删除 2、倒数第 K 个节点...
  • 带头结点的单链表中删除一个最小值结点的算法。 Node.java /* * 节点类的泛型定义 */ public class Node<T> { T data; Node<T> next; public Node(Node<T> n){ next = n; } public ...
  • 实现方式很多,这里只说...2.满足上面条件后,定义NodeList P=head,重头开始遍历链表,走k步后,退出循环(此循环,如果没到K不p就为null了,说明没有倒数第K个节点,k大于表长度了,直接返回head)。 3.定义Nod

空空如也

空空如也

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

在单链表中删除一个节点