数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
1
每日一练
1．编写一个算法来交换单链表中指针 P 所指结点与其后继结点，HEAD 是该链表的头指针，P 指向该链表 中某一结点。类似本题的另外叙述有：
(1) 已知非空线性链表第一个结点由 List 指出，请写一算法，交换 p 所指的结点与其下一个结点在链表中的位置(设 p 指向的不是链表最后那个结点)。
(2) 已知任意单链表如图所示(编者略去图)。Head 为表头指针，指向表的第一个元素，p 为指向表中任意 结点的指针，试设计一个算法，将 p 指向的结点和其后面结点交换位置（可采用任何高级语言描述算法）。
正确答案
ps：||代表注释
1. [题目分析] 单链表中查找任何结点，都必须从头指针开始。本题要求将指针p所指结点与其后继结点 交换，这不仅要求知道p结点，还应知道p的前驱结点。这样才能在p与其后继结点交换后，由原p结点的前驱来 指向原p结点的后继结点。 另外，若无特别说明，为了处理的方便统一，单链表均设头结点，链表的指针就是头结点的指针。并且由 于链表指针具有标记链表的作用，也常用指针名冠以链表名称。如“链表head”既指的是链表的名字是head， 也指出链表的头指针是head。
LinkedList Exchange（LinkedList HEAD，p） ∥HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后继结点交换。
{q=head->next； ∥q是工作指针，指向链表中当前待处理结点。
pre=head； ∥pre是前驱结点指针，指向q的前驱。
while（q!=null && q!=p）
{pre=q；q=q->next；} ∥未找到p结点，后移指针。
if（p->next==null）printf（“p无后继结点\n”）; ∥p是链表中最后一个结点，无后继。 else∥处理p和后继结点交换
{q=p->next； ∥暂存p的后继。
pre->next=q； ∥p前驱结点的后继指向p的后继。
p->next=q->next；∥p的后继指向原p后继的后继。
q->next=p ；∥原p后继的后继指针指向p。
} }∥算法结束。
类似本题的其它题目的解答：
（1）与上面基本相同，只是明确说明“p指向的不是链表最后那个结点。”
（2）与上面题基本相同，仅叙述不同，故不再作解答。