编程 单向链表特殊操作

扩展问题1：查找单向链表中的倒数第k个节点。

思路：按照遍历查找链表的常用模式，可能会马上想到一种简单的方法就是：先遍历链表，看一下链表中有多少个节点。假设链表中有n个节点，那么要找倒数第k个，也就是正数n-k+1个了。接下来，只要指针从头向后走n-k步就可了。这种方法大约要执行2n-k次。

      那么，有没有比上面的方法更高效的方法呢？把思维打开，不要固定在遍历链表的时候只能用有一个指针的思维定式上。我们可以尝试用多个指针以不同的次序开始遍历链表。

      对于，这个问题，我们就可以设置两个指针，一个指针先在链表上走K步，然后另一个指针从链表头开始和前一个指针一起向后走，这样当第一个指针到达链表尾部时候，第二个指针就会在第一个指针前面k个结点处。这时就找到了倒数第K个节点，算法执行的次数为n 次,比上一个方法减少了一些步,如图4。



图4 查找倒数第k个节点

代码实现：

gleList* returnNodeFromBack(SingleList* head,int k)

//返回链表中的倒数第K节点的指针//输入参数：单链表的头指针，要查找的节点的倒数位置//输出参数：无//返回值：成功返回节点指针，失败返回NULLSingleList* returnNodeFromBack(SingleList* head,int k){    SingleList *firstPtr,*secondPtr;    int count = 0;    firstPtr = secondPtr = head;    while((firstPtr)&&(count < k))    {        firstPtr = firstPtr->next;        count++;    }    if(count < k)    {        return NULL;    }    while(firstPtr)    {        firstPtr = firstPtr->next;        secondPtr = secondPtr->next;    }    return secondPtr;}扩展问题2：查找单向链表中的中间节点，当节点个数为偶数时返回中间两个元素中的前者（后者）

思路：类似于第一个扩展问题，对于查找中间元素，我们首先也可以利用先遍布链表看一看总共有多少个节点，然后再走节点总个数的一半即可找到中间元素。显然，这种方法也是要遍历两次链表。

      那么，能不能借鉴上面的改进方法再来改进一下这个问题呢。当然可以，在此问题中依然使用两个遍历指针。让第一个指针每次走两步，第二个指针每次走一步，这样因为第一个指针经过的节点数是第二指针的两倍，所以当第一个指针到达中点时，第二个指针正好处于链表的中间位置。

代码实现：

SingleList* returnMidNode(SingleList* head)

//返回链表的中间节点//输入参数：单链表的头指针//输出参数：无//返回值：中间节点的指针或NULLSingleList* returnMidNode(SingleList* head){    SingleList *firstPtr,*secondPtr;    firstPtr = secondPtr = head;    //链表中没有节点或只有一个节点    if((firstPtr == NULL) || (firstPtr->next == NULL))    {        return firstPtr;    }    //while((firstPtr)&&(firstPtr->next))  //偶数个数时返回中间两个索引较大者    while((firstPtr->next)&&(firstPtr->next->next))//偶数个数时返回中间两个索引较小者    {        firstPtr = firstPtr->next->next;        secondPtr = secondPtr->next;    }    return secondPtr;}


扩展问题：返回两个链表的第一个交点?

      仔细阅读上一个问题的思路，可发现思路中第一种解决方法就可以解决这个问题。但其时间的复杂度为O（n2）。那么能不能仿照第二种方法一样来提高算法的效率呢？答案，当然是可以。

      分析两个相交链表的性质可知，如果相交，则交点之后的链表节点同时属于这两个链表。由此可以推断出，交点之后每条链表上节点的个数肯定是相同的。因此，如果两条链表节点的个数分别为len1和len2(len1>len2)，那么他们的第一个交点在第一条链表上肯定是第(len1-len2)个节点之后的某个节点。

      总结上面的分析，我们得出一算法：

            （1）先分别遍历一遍两条链表，求出两链表各自的节点个数len1和len2。

            （2）让节点多的链表先走|len1-len2|

            （3）两条链表同时向后步进，并判断节点是否相同。第一个相同点就是第一个交点。

代码实现：

view sourceprint?01 //求两条单向链表的第一个交点 

02 //输入参数：两个单链表的头指针 

03 //输出参数：无 

04 //返回值：相交返回第一个交点指针,不相交返回NULL 

05 SingleList* FirstIntersectNode(SingleList *head1,SingleList *head2) 

06 { 

07     SingleList *firstPtr = head1,*secondPtr = head2; 

08     int len1 = 0,len2 = 0;  

09   

10     //循环遍历第一个链表 

11     while(firstPtr) 

12     { 

13         firstPtr = firstPtr->next; 

14         len1++; 

15     } 

16   

17     //循环遍历第二个链表 

18     while(secondPtr) 

19     { 

20         secondPtr = secondPtr->next; 

21         len2++; 

22     } 

23   

24     firstPtr = head1; 

25     secondPtr = head2; 

26   

27     //让指向较长链表的指针，先走出长出的几步 

28     if(len1 > len2) 

29     { 

30         for(int i=0; i < (len1-len2);i++) 

31         { 

32             firstPtr = firstPtr->next; 

33         } 

34     } 

35     else

36     { 

37         for(int i=0; i < (len2-len1);i++) 

38         { 

39             secondPtr = secondPtr->next; 

40         } 

41     } 

42     while(firstPtr&&secondPtr) 

43     { 

44         if(firstPtr == secondPtr) 

45         { 

46             return firstPtr; 

47         } 

48         firstPtr = firstPtr->next; 

49         secondPtr = secondPtr->next; 

50     } 

51     return NULL; 

52 }