Question

问： 20 求3道C++的题目。 1、定义两个同种的单向链表（结点中包含一个整型数和一个指向本结

问： 20 求3道C++的题目。
1、定义两个同种的单向链表（结点中包含一个整型数和一个指向本结点类型的指针），该两个链表中数据已排序好，编制程序，合并这两个链表。
2、已知head指向一个带头结点的双向链表，链表中每个结点包含字符型数据域(data)和指向下一个结点的指针域(next)。请编写函数实现在值为a的结点前插入值为key的结点，若没有值为a的结点，则将插在链表的最后。
3、模拟人工洗牌。编写一个模拟人工洗牌的程序，将洗好的牌分别发给4个人。

• 你的回答被采纳后将获得：
• 系统奖励15（财富值+成长值）+难题奖励20（财富值+成长值）

Answer 1

就是给你一个单链表，要你获得单链表中位置中间的结点？你会怎么做？
一般我们可能用一个指针，从头到尾撸一遍，同时记录单链表的长度，然后再除以2得出第几
项为中间结点，然后再撸length / 2获得中间节点，重复遍历很繁琐，有没有其他的方法呢？
有，肯定有，这里提供一个简单的方法：
用两个不同的指针，按照不同的移动顺序来移动，这里我们暂且把他们成为快慢指针！
每次循环，
**快指针向后移动两个结点： p = p -> next -> next；
慢指针向后移动一个结点： q = q -> next;**
当快指针到达尾部的时候，慢指针不就指向中间结点了，你说是吧~