关于链表的几个面试题

Question1：输入一个单链表，输出倒数第k个节点的值；

分析：最自然的想法就是先走到链表的尾端，然后回溯k个节点。但是单链表只有从前往后的指针，所以不能向前回溯。再进一步分析，假设链表有n个节点，那么倒数第k个节点就是从头节点开始的第n-k+1个节点，这种想法只需要遍历一遍链表，得到总的节点数就行了，也就是说我们需要遍历这个链表两次。

　　但是还有一种方法只需要遍历一遍链表：我们可以声明两个指针p1和p2；p1从链表的头指针开始向前走k-1步，p2保持不动；从第k步开始，p1和p2通知向前走，当p1是尾指针时，p2指向的就是倒数第k个指针。这是因为：两个指针的距离保持在k-1，才会有这种规律。

 1 ListNode* FindKthToTail(ListNode* pListHead, int k){
 2     if(pListHead==NULL || k==0){
 3         return NULL;
 4     }
 5     ListNode* pAhead=pListHead;
 6     ListNode* pBehind=NULL;
 7     
 8     for(int i=0;i<k-1;i++){
 9         if(pAhead->m_pNext != NULL)
10             pAhead=pAhead->m_pNext;
11         else
12             return NULL;
13     }
14     
15     pBehind=pListHead;
16     while(pAhead->m_pNext!=NULL){
17         pAhead=pAhead->m_pNext;
18         pBehind=pBehind->m_pNext;
19     }
20     return pBehind;
21 }

Question2：输入一个单链表，将其翻转，并输出翻转后的头指针。

分析：除了注意指针的边界条件之外，要实现翻转操作，还必须加多一个指针保存当前节点的信息。

 1 ListNode* ReverseList(ListNode* pHead){
 2     ListNode* pReverseHead=NULL;
 3     ListNode* pNode=pHead;
 4     ListNode* pPrev=NULL;
 5     while(pNode!=NULL){
 6         ListNode* pNext=pNode->m_pNext;
 7         if(pNext==NULL){
 8             pReverseHead=pNode;
 9         }
10         pNode->m_pNext=pPrev;
11         
12         pPrev=pNode;
13         pNode=pNext;
14     }
15     return pReverseHead;
16 }