（一）题目：输入一个单项链表，找出该链表的倒数第k个节点。
解法：设立两个指针，，先让第一个指针先往前走k步，然后第二个指针放到链表开头。
然后两个链表一起往后走，当第一个链表到达链表尾部的时候，后面那个链表所在的位置就刚好是链表的倒数第k个节点！
代码：
struct node {int data;node *pNext;};node* funtion(node *head, int k) {assert(k >= 0);node *pOne, *pTwo;pOne = head;pTwo = head;for(; k >0 && pTwo != NULL; k–) {pTwo = pTwo->pNext;}if(k > 0) return NULL;while(pTwo != NULL) {pOne = pOne -> pNext;pTwo = pTwo -> pNext;}return pOne;}
（二）题目：给定两个单项链表，给定这两个单项链表的头指针，编程判断这两个链表是否相交。
方法：因为两个链表如果相交的话，那么从相交节点开始，到最后，这两个链表的后面的部分都是公共的部分！
所以，只需要分别从两个链表开头，遍历到最后结尾处，看看两个尾部是不是相同的一个节点！如果是的话，说明这两个链表是相交的，如果不是的话，说明这两个 链表是不相交的。
题目：上面说的这种方法是两个链表都不带环，但是如果链表带了环呢！？
所以总的方法：
（1）先判断两个链表带不带环
（2）如果都不带环，就判断两个链表的尾节点是否相等。
（3）如果都带环，判断一链表上两个指针相遇的那个节点，在不在另外一条链表上。如果在的话，则两个链表相交。如果不在的话，则不相交。
代码：
struct node {int data;node *pNext;};bool isCircle(node *head, node *&circleNode, node *&lastNode) {node *fast = head -> pNext;node *slow = head;while(fast && slow && fast != slow) {if(fast -> pNext != NULL) fast = fast -> pNext;if(fast -> pNext == NULL) lastNode = fast;if(slow -> pNext == NULL) lastNode = slow;fast = fast -> pNext;slow = slow -> pNext;}if(fast == slow && fast && slow) {circleNode = fast;return true;} else return false;}bool detect(node *head1, node *head2) {node *circleNode1;node *circleNode2;node *lastNode1;node *lastNode2;bool isCircle1 = isCircle(head1, circleNode1, lastNode1);bool isCircle2 = isCircle(head2, circleNode2, lastNode2);if(isCircle1 != isCircle2) return false;//两个链变一个有环，一个无环else if(!isCircle1 && !isCircle2) return lastNode1 == lastNode2;//两个链表都无环else {//两个链表都有环node *temp = circleNode1 -> pNext;while(temp != circleNode1) {if(temp == circleNode2) return true;temp = temp -> pNext;}return false;}return false;}
（三）求两个链表相交的第一个节点
方法，思路：先求出更长的那个链表的，然后在这个链表上面先走长度之差的步数，然后两个指针在一起走，走到最后，既是同一个节点！
struct node {int data;node *pNext;};unsigned int ListLength(node *pHead) {unsigned int nLength = 0;node *pNode = pHead;while(pNode != NULL) {nLength++;pNode = pNode -> pNext;}return nLength;}node* FindFirstCommonNode(node *pHead1, node *pHead2) {unsigned int nLength1 = ListLength(pHead1);unsigned int nLength2 = ListLength(pHead2);int nLengthDiff = nLength1 – nLength2;node *pListHeadLong = pHead1;node *pListHeadShort = pHead2;if(nLength1 < nLength2) {nLengthDiff = nLength2 – nLength1;pListHeadLong = pHead2;pListHeadShort = pHead1;}for(int i = 0; i < nLengthDiff; ++i) pListHeadLong = pListHeadLong -> pNext;while(pListHeadLong != NULL && pListHeadShort != NULL && pListHeadLong != pListHeadShort) {pListHeadLong = pListHeadLong -> pNext;pListHeadShort = pListHeadShort -> pNext;}node *pFirstCommonNode = NULL;if(pListHeadLong == pListHeadShort) pFirstCommonNode = pListHeadLong;return pFirstCommonNode;}
上帝助自助者。
