2.2.2　算法设计

1.已知非空线性链表的第一个结点由list指出，试写一算法，交换p所指结点与其下一结点在链表中的位置(设p指向的不是链表最后那个结点)。

【解答】 整个算法分成两个部分：(1)确定p的位置，同时给出p的前驱；(2)将结点*p与p的后继结点交换。在交换*p与p的后继结点时，不仅要考虑两个结点内部指针的变化，而且还应该考虑p的前驱结点的指针问题。在p已确定的情况下，此题求解的核心步骤如下：

(1) 改变p的前驱结点的next指针指向p的下一个结点；

(2) 改变p的next的值为p的后继结点的next值；

(3) 改变原p的后继结点的next值为指向p。

实现算法如下：

2. 设有头结点的单链表L，编程对表中任一值只保留一个结点，删除其余值相同的结点。

【解答】 算法可按如下方法设计：

(1) 首先用指针p指向链表中第一个数据结点，然后用指针t搜索整个链表以寻找值相同的结点直至链尾。在搜索中，指针s指向t所指结点前驱结点。当t-＞data=p-＞data时，删除t所指结点，即s-＞next=t-＞next。

(2) 修改指针p，使p指向链表的下一个结点(即p=p-＞next)，然后重复(1)的操作直至p=NULL。

算法实现如下：

3. 有两个循环链表，链头指针分别为L₁和L₂，要求将L₂链接表链到L₁反应链表之后，且链接后仍保持循环链表形式，试写出程序并估计时间复杂度。

【解答】 实现的算法如下：

时间复杂度为O(n)。

4. 已知递增有序的单链表A、B分别存储了一个集合，请设计算法以求出两个集合A和B的差集A—B(即仅由在A中出现而不在B中出现的元素所构成的集合)，并以同样的形式存储，同时返回集合的元素个数。

【解答】 算法实现如下：

5. 设head为单链表的头指针,并设单链表带有头结点,编写算法将单链表中的数据元素按照数据元素的值递增有序的顺序进行就地排序。

【解答】 算法思想：把头指针head所指单链表置空后，把原单链表(设由头指针p指示)中的数据元素逐个重新插入。每次插入从head所指单链表的当前首元结点开始，逐个比较head所指单链表每个结点的data域值和p所指单链表的当前首元结点的data域值，当前者小于或等于后者时，用head所指单链表的下一个结点进行比较；否则就找到了插入结点的合适位置，从p所指单链表中取当前首元结点插入到head所指单链表的合适位置。这样的过程一直进行到p所指单链表为空时结束。

算法设计如下：