其中，curr2.Next = curr1.Next.Next; 这句话是关键，它负责把上一个单链表的表尾和下一个单链表的非空表头连接起来。
7.单链表交换任意两个元素（不包括表头）
先一次遍历找到这两个元素curr1和curr2，同时存储这两个元素的前驱元素pre1和pre2。 然后大换血
public static Link SwitchPoints(Link head, Link p, Link q) {
if (p == head || q == head)
throw new Exception(\ if (p == q)
return head;
//find p and q in the link Link curr = head; Link curr1 = p; Link curr2 = q; Link pre1 = null; Link pre2 = null;
int count = 0; while (curr != null) {
if (curr.Next == p) {
pre1 = curr; count++;
if (count == 2) break; }
else if (curr.Next == q) {
pre2 = curr; count++;
if (count == 2) break; }
curr = curr.Next; }
curr = curr1.Next;
pre1.Next = curr2;
curr1.Next = curr2.Next; pre2.Next = curr1; curr2.Next = curr; return head; }
注意特例，如果相同元素，就没有必要交换；如果有一个是表头，就不交换。
8.判断单链表是否有环？如何找到环的“起始”点？如何知道环的长度？
算法思想：
先分析是否有环。为此我们建立两个指针，从header一起向前跑，一个步长为1，一个步长为2，用while（直到步长2的跑到结尾）检查两个指针是否相等，直到找到为止。
static bool JudgeCircleExists(Link head) {
Link first = head; //1 step each time Link second = head; //2 steps each time
while (second.Next != null && second.Next.Next != null) {
second = second.Next.Next; first = first.Next; if (second == first) return true; }
return false; }
那又如何知道环的长度呢？
根据上面的算法，在返回true的地方，也就是2个指针相遇处，这个位置的节点P肯定位于环上。我们从这个节点开始先前走，转了一圈肯定能回来： static int GetCircleLength(Link point) {
int length = 1; Link curr = point;
while (curr.Next != point) {
length++;
curr = curr.Next;
}
return length; }
继续我们的讨论，如何找到环的“起始”点呢？
延续上面的思路，我们仍然在返回true的地方P，计算一下从有环单链表的表头head到P点的距离
static int GetLengthFromHeadToPoint(Link head, Link point) {
int length = 1; Link curr = head; while (curr != point) {
length++;
curr = curr.Next; }
return length; }
如果我们把环从P点“切开”（当然并不是真的切，那就破坏原来的数据结构了），那么问题就转化为计算两个相交“单链表”的交点（第10题）： 一个单链表是从P点出发，到达P（一个回圈），距离M；另一个单链表从有环单链表的表头head出发，到达P，距离N。
我们可以参考第10题的GetIntersect方法并稍作修改。 private static Link FindIntersect(Link head) {
Link p = null;
//get the point in the circle
bool result = JudgeCircleExists(head, ref p); if (!result) return null; Link curr1 = head.Next; Link curr2 = p.Next; //length from head to p int M = 1;
while (curr1 != p) {
M++;
curr1 = curr1.Next; }
//circle length int N = 1;
while (curr2 != p)
{
N++;
curr2 = curr2.Next; }
//recover curr1 & curr2 curr1 = head.Next; curr2 = p.Next;
//make 2 links have the same distance to the intersect if (M > N) {
for (int i = 0; i < M - N; i++) curr1 = curr1.Next; }
else if (M < N) {
for (int i = 0; i < N - M; i++) curr2 = curr2.Next; }
//goto the intersect while (curr1 != p) {
if (curr1 == curr2) {
return curr1; }
curr1 = curr1.Next; curr2 = curr2.Next; }
return null; }
9.判断两个单链表是否相交
这道题有多种算法。
算法1：把第一个链表逐项存在hashtable中，遍历第2个链表的每一项，如果能在第一个链表中找到，则必然相交。
static bool JudgeIntersectLink1(Link head1, Link head2) {
Hashtable ht = new Hashtable(); Link curr1 = head1; Link curr2 = head2;
//store all the elements of link1
while (curr1.Next != null) {
ht[curr1.Next] = string.Empty; curr1 = curr1.Next; }
//check all the elements in link2 if exists in Hashtable or not while (curr2.Next != null) {
//if exists
if (ht[curr2.Next] != null) {
return true; }
curr2 = curr2.Next; }
return false; }
算法2：把一个链表A接在另一个链表B的末尾，如果有环，则必然相交。如何判断有环呢？从A开始遍历，如果能回到A的表头，则肯定有环。 注意，在返回结果之前，要把刚才连接上的两个链表断开，恢复原状。 static bool JudgeIntersectLink2(Link head1, Link head2) {
bool exists = false; Link curr1 = head1; Link curr2 = head2;
//goto the end of the link1 while (curr1.Next != null) {
curr1 = curr1.Next; }
//join these two links curr1.Next = head2; //iterate link2
while (curr2.Next != null) {
if (curr2.Next == head2) {
exists = true; break; }
curr2 = curr2.Next;
算法大全-面试题-数据结构
