careercup-链表 2.3

简介: 2.3 实现一个算法,删除单向链表中间的某个结点,假设你只能访问该结点。(即你不知道头结点) 这个问题的关键是你只有一个指向要删除结点的指针,如果直接删除它,这条链表就断了。 但你又没办法得到该结点之前结点的指针,是的,它连头结点也不提供。

2.3 实现一个算法,删除单向链表中间的某个结点,假设你只能访问该结点。(即你不知道头结点)

这个问题的关键是你只有一个指向要删除结点的指针,如果直接删除它,这条链表就断了。 但你又没办法得到该结点之前结点的指针,是的,它连头结点也不提供。在这种情况下, 你只能另觅他径。重新审视一下这个问题,我们只能获得从c结点开始后的指针, 如果让你删除c结点后的某个结点,那肯定是没问题的。比如删除结点d,那只需要把c 的next指针指向e,然后delete d就ok了。好的,如果我们就删除结点d,我们将得到 a->b->c->e,和目标链表只差了一个结点。怎么办呢?把d的数据给c! 结点结构都是一样的,删除谁都一样,最关键的是结点中的数据,只要我们留下的是数据 a->b->d->e就OK了

思路已经有了,直接写代码?等等,写代码之前,让我们再简单分析一 下可能出现的各种情况(当然包括边界情况)。如果c指向链表的:1.头结点;2.中间结点。 3.尾结点。4.为空。情况1,2属于正常情况,直接将d的数据给c,c的next指针指向d 的next指向所指结点,删除d就OK。情况4为空,直接返回。情况3比较特殊,如果c 指向尾结点,一般会认为直接删除c就ok了,反正c后面也没有结点了,不用担心链表断开。 可是真的是这样吗?代码告诉我们,直接删除c,指向c的那个结点(比如说b)的next指针 并不会为空。也就是说,如果你打印这个链表,它还是会打印出和原来链表长度一样的链表, 而且最后一个元素为0

 

关于这一点,原书CTCI中是这么讲的,这正是面试官希望你指出来的。然后, 你可以做一些特殊处理,比如当c是尾结点时,将它的数据设置为一些特殊字符, 这样在打印时就可以不打印它。当然也可以直接不处理这种情况,原书里的代码就是这么做 的。这里,也直接不处理这种情况。

  C++实现代码:

#include<iostream>
#include<new>
using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(NULL) {}
};

void createList(ListNode *&L)
{
    int arr[10]= {1,2,3,2,5,6,7,3,9,1};
    int i;
    ListNode *p=NULL;
    for(i=0; i<10; i++)
    {
        ListNode *tmp=new ListNode(arr[i]);
        if(L==NULL)
        {
            L=tmp;
            p=tmp;
        }
        else
        {
            p->next=tmp;
            p=tmp;
        }
    }
}

void deleteNode(ListNode *c)
{
    if(c==NULL||c->next==NULL)
        return;
    ListNode *d=c->next;
    c->next=d->next;
    c->val=d->val;
    d->next=NULL;
    delete(d);
}

int main()
{
    ListNode *head=NULL;
    createList(head);
    ListNode *p=head;
    while(p)
    {
        cout<<p->val<<" ";
        p=p->next;
    }
    cout<<endl;
    deleteNode(head->next->next->next);
    p=head;
        while(p)
    {
        cout<<p->val<<" ";
        p=p->next;
    }
    cout<<endl;
}

 

相关文章
careercup-链表 2.1
2.1 编写代码,移除未排序链表中的重复节点。 不使用临时缓存: 如果不允许使用临时的缓存(即不能使用额外的存储空间),那需要两个指针, 当第一个指针指向某个元素时,第二个指针把该元素后面与它相同的元素删除, 时间复杂度O(n2 )。
814 0
|
机器学习/深度学习 C++ 算法
careercup-链表 2.2
2.2 实现一个算法,找到单链表中倒数第k个节点。 这道题的考点在于我们怎么在一个单链表中找到倒数第n个元素? 由于是单链表,所以我们没办法从最后一个元素数起,然后数n个得到答案。 但这种最直观的思路显然是没错的,那我们有没有办法通过别的方式,从最后的元素数起数 n个来得到我们想要的答案呢。
787 0
|
C++ Perl
careercup-链表 2.4
2.4 编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前。 思路:将小于的结点还是保存在原来的链表中,将大于等于x的结点加入一个新的链表,最后将这两个链表链接起来。
642 0
careercup-链表 2.5
2.5 给定两个用链表表示的整数,每个结点包含一个数位。这些数位是反向存放的,也就是个位排在链表首部。编写函数对这两个整数求和,并用链表形式返回结果。 示例: 输入: (7->1->6)+(5->9->2),即617+295.
748 0
|
算法 C++ Perl
careercup-链表 2.6
2.6 给定一个有环链表,实现一个算法返回环路的开头结点。 类似leetcode中 Linked List Cycle II C++实现代码: #include #include using namespace std; struct ListNode { int v...
716 0
|
C++ Perl
careercup-链表 2.7
2.7 编写一个函数,检查链表是否为回文。 思路:1)可以利用链表中的元素采用头插法创建一个新的链表,然后比较两个链表的元素是否相等。      2)利用快慢指针,将链表后半部分逆转之后,比较前半部分与后半部分是否相等。
785 0
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
146 2