【编程之好】读书笔记：从无头单链表中删除结点

【编程之美】读书笔记：从无头单链表中删除结点

        问题：假设有一个没有头指针的单链表。一个指针指向此单链表中间的一个节点(不是第一个也不是最后一个)，如何将该结点删除？

        分析：假设给定的指针为pCurrent,Node *pNext=pCurrent->Next(pNext指向pCurrent的下一个结点)。根据题意，pNext!=NULL.

若pCurrent指向中间要删除的节点B，如下图所示：

但是该链表没有头指针，无法扫描到结点A。但是我们可以换一种思路，可以将结点C的数据赋给B，然后将真正的C结点删除，因为删除C结点是很方便的，知道其前驱结点。

可以用下面代码实现：

pCurrent->Next=pNext->Next;

pCurrent->Data=pNext->Data;

delete pNext;

代码如下：

void DeleteNode(node * pCrrent)
{
Assert(pCurrent!=NuLL)
node *pNext=pCurrent->next;
if(pNext!=NULL)
{
pCurrent->Next=pNext->Next;
pCurrent->Data=pNext->Data;
delete pNext;
}

}

扩展问题：给定一个链表的头指针，只要求一次遍历，求单链表中的元素顺序反转过来。

可以用单链表的首插法来实现逆转。

代码如下：

void reverse(node *&head)
{
node *p,*s;
p=head->next;//取得头节点的后一个节点
head->next=NULL;//将头节点单独拿出来
//应用首插入法逆转
while(p!=NULL)
{
s=p; //将待插入的节点保存
p=p->next;
//开始插入
s->next=head->next;
head->next=s;
}
}

附加问题：没有头结点的单链表逆转问题

      这里用三个辅助指针来完成逆转，也可以给单链表加上一个头指针，采用上面的首插法逆转，逆转完成后删除首结点。

   代码如下：

void reverse(node *&head)
{
node *p,*q,*r;
p=head;
q=p->next;
while(q!=NULL)
{
r=q->next;
//开始逆转
q->next=p;
p=q;
q=r;
}
head->next=NULL; 将第一个节点的next置为空
head=p; //将p改为头节点
}