《算法之美》例题

结构之法——字符串及链表的探索

【3.4 拓展问题】编写一个函数，给定一个链表的头指针，要求只遍历一次，将单链表中的元素顺序反转过来。

思路：遍历每一个结点，当前结点指向上一个节点的地址。

伪代码如下：

1 node *prev_node = null;//上一个节点
2 node *now_node;//头结点
3 while((*now_node)!=null){
4     node *temp = now_node;
5     now_node = now_node->next;
6     temp->next = prev_node;
7     prev_node = temp;
8 }

【3.6 判断两个链表是否相交】一个大的系统中，如果出现两个链表相交的情况，而且释放了其中一个链表的所有节点，那样就会造成信息的丢失，并且另一个与之相交的链表也会受到影响，这是我们不希望看到的。

解法一：直接遍历

解法二：根据上图可以发现链表相交的特点最后的节点相同，判断两个链表的最后一个节点是否相同。