《编程之美》3.4:没有头结点的单链表如何删除结点

一个巧妙的思路
服务器君一共花费了956.510 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

题目:假设有一个没有头结点的单链表。一个指针指向此单链表中间的一个节点(非第一个节点, 也非最后一个节点)。请将该节点从单链表中删除。

典型的“狸猫换太子”, 若要删除该节点,正常情况下,应该要知道该节点的前面节点的指针,但是由于单链表中没有头结点,所以无法追溯到该节点前面的那个节点,因此,这里采用了“移花接木”的方法。设该节点为B,下一个节点为C。那么,首先将B节点的内容替换为C节点的内容,然后,将C节点删除,这样就达到了我们的目的。代码如下:

pcur->next = pnext->next;
pcur->data = pnext->date;
delete pnext;

具体程序实现:

#include "stdafx.h"
 
struct Node
{
    int value;
    Node * next;
};
 
//不考虑删除节点为尾节点
void deleteNode(Node * pCurrent)
{
    if(pCurrent != NULL)
    {
        if(pCurrent->next != NULL)
        {
            Node * pTemp = pCurrent->next;
            pCurrent->value = pTemp->value;
            pCurrent->next = pTemp->next;
            delete pTemp;
        }
    }
 
}
 
 
//考虑删除节点为尾节点
void deleteNode2(Node * pCurrent, Node * head)
{
    if(pCurrent != NULL)
    {
        if(pCurrent->next != NULL)
        {
            Node * pTemp = pCurrent->next;
            pCurrent->value = pTemp->value;
            pCurrent->next = pTemp->next;
            delete pTemp;
        }
        else
        {
            Node * temp = head;
            while(temp != NULL)
            {
                if(temp->next == pCurrent)
                {
                    delete pCurrent;
                    temp->next = NULL;
                }
                temp = temp->next;
            }
        }
    }
 
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    Node * n1 = new Node();
    Node * n2 = new Node();
    Node * n3 = new Node();
    n1->value = 1;
    n1->next = n2;
    n2->value = 2;
    n2->next = n3;
    n3->value = 3;
    n3->next = NULL;
 
    printf("before delete:");
    Node * temp = n1;
    while(temp!=NULL)
    {
        printf("%d ", temp->value);
        temp = temp->next;
    }
 
    printf("after delete:");
    deleteNode2(n3, n1);
    temp = n1;
    while(temp!=NULL)
    {
        printf("%d ", temp->value);
        temp = temp->next;
    }
 
    return 0;
}

类似问题:

  1. 从无头单链表中删除节点问题:假设有一个没有头指针的单链表,一个指针p指向单链表中的一个节点(不是第一个,也不是最后一个),请将该节点删除掉。
  2. 向无头单链表中添加节点问题:假设有一个没有头指针的单链表,一个指针p指向单链表中的一个节点(不是第一个,也不是最后一个),请在该节点之前插入一个新的节点q。

由于链表是无头单向链表,所以我们无法由当前节点获得p的前一节点,而无论是删除当前节点还是向前面节点插入新节点都需要获得p的前一节点。在这里我们不妨换一下思路,对当前节点的后继结点进行操作,然后将前后节点的数据进行适当交换也可以得到相应效果。

问题1解法:将p后继结点p->next的数据拷贝到p,然后删除p->next,这样就达到了相同的效果,代码如下:

ListNode* p_next = p->next;
p->value=p_next->value;
p->next=p_next->next;
delete   p_next;

问题2解法:在p节点后添加q,然后交换p和q的数据即可。

q->next=p->next;
p->next=q;
swap(&p->value, &q->value);

扩展问题:将一个单链表,在只遍历一遍的情况下,将单链表中的元素顺序反转过来。

解答:可以用三个指针进行遍历,在遍历的途中,进行逆置。

本文地址:http://www.nowamagic.net/librarys/veda/detail/1826,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1826

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《编程珠玑(第2版)》 Jon Bentley (作者), 黄倩 (译者), 钱丽艳 (译者)

《编程珠玑(第2版)》是计算机科学方面的经典名著。书的内容围绕程序设计人员面对的一系列实际问题展开。作者Jon Bentley 以其独有的洞察力和创造力,引导读者理解这些问题并学会解决方法,而这些正是程序员实际编程生涯中至关重要的。

更多计算机宝库...