鏈表中倒數第K個結點，倒數結點

鏈表中倒數第K個結點，倒數結點

題目：輸入一個鏈表，輸出該鏈表中倒數第K個結點。為了符合大多數人的習慣，本題從1開始計數，即鏈表的尾結點是倒數第1個結點。例如一個鏈表有6個結點，從頭結點開始它們的值依次是1、2、3、4、5、6。這個鏈表的倒數第3個結點是值為4的結點。

思路:設定兩個指針p1和p2，兩個指針剛開始都指向鏈表的第一個結點，然後讓p1指針先走(k-1)步，然後再讓兩個指針一起往後走，當p1指針指向鏈表最後一個結點的時候，p2指針剛好指向鏈表中的倒數第k個結點。

在寫代碼的時候需要考慮魯棒性，最好采用防御性編程，就是考慮在哪些地方會出錯，然後提前加上錯誤判斷，這樣避免因此錯誤輸入而導致程序崩潰。

  1 #include<iostream>
  2 #include<stdio.h> 
  3 #include<tchar.h>
  4 using namespace std;
  5 
  6 //鏈表結構
  7 struct ListNode
  8 {
  9     int m_nValue;
 10     ListNode* m_pNext;
 11 };
 12 
 13 //創建一個鏈表結點
 14 ListNode* CreateListNode(int value)
 15 {
 16     ListNode* pNode = new ListNode();
 17     pNode->m_nValue = value;
 18     pNode->m_pNext = NULL;
 19 
 20     return pNode;
 21 }
 22 
 23 //輸出鏈表中的某一結點的值
 24 void PrintListNode(ListNode* pNode)
 25 {
 26     if(pNode == NULL)
 27             printf("The node is NULL\n");
 28     else
 29             printf("The key in node is %d.\n", pNode->m_nValue);
 30 }
 31 
 32 //輸出鏈表 
 33 void PrintList(ListNode* pHead)
 34 {
 35     ListNode *pNode = pHead;
 36     while(pNode != NULL)
 37     {
 38         cout << pNode->m_nValue<< " ";
 39         pNode = pNode->m_pNext;
 40     }
 41     cout<<endl;
 42 }
 43 
 44 //刪除結點 
 45 void DestroyList(ListNode* pHead)
 46 {
 47     ListNode* pNode = pHead;
 48     while(pNode != NULL)
 49     {
 50         pHead = pHead->m_pNext;
 51         delete pNode;
 52         pNode = pHead;
 53     }
 54 }
 55 
 56 //往鏈表末尾添加結點
 57 /*
 58 注意這裡pHead是一個指向指針的指針，在主函數中一般傳遞的是引用。
 59 因為如果要為鏈表添加結點，那麼就會修改鏈表結構，所以必須傳遞引用才能夠保存修改後的結構。
 60 */
 61 void AddToTail(ListNode** pHead, int value)
 62 {
 63     ListNode* pNew = new ListNode();
 64     pNew->m_nValue = value;
 65     pNew->m_pNext = NULL;
 66 
 67     if(*pHead == NULL)
 68     {
 69         *pHead = pNew;
 70     }
 71     else
 72     {
 73         ListNode* pNode = *pHead;
 74         while(pNode->m_pNext != NULL)
 75             pNode = pNode->m_pNext;
 76 
 77         pNode->m_pNext = pNew;
 78     }
 79 }
 80 
 81 
 82 //鏈接兩個結點 
 83 //void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)
 84 //{
 85 //    if(pCurrent == NULL)
 86 //    {
 87 //        printf("Error to connect two nodes.\n");
 88 //        exit(1);
 89 //    }
 90 //    pCurrent->m_pNext = pNext;
 91 //}
 92 
 93 //防御性編程，魯棒性更好
 94 ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
 95 {
 96     if(pListHead == NULL || k == 0)
 97             return NULL;
 98 
 99     ListNode *pAhead = pListHead;
100     ListNode *pBehind = NULL;
101 
102     for(unsigned int i = 0 ; i < k- 1 ; i ++)
103     {
104         if(pAhead->m_pNext != NULL)
105             pAhead = pAhead->m_pNext;
106         else
107             return NULL;
108     }
109     
110     pBehind = pListHead;
111     while(pAhead->m_pNext != NULL)
112     {
113         pAhead = pAhead->m_pNext;
114         pBehind = pBehind->m_pNext;
115     }
116 
117     return pBehind;
118 }
119 
120 int main()
121 {
122     //創建結點
123     ListNode* pNode1=CreateListNode(1);//創建一個結點
124     PrintList(pNode1);//打印
125     //往鏈表中添加新結點
126     AddToTail(&pNode1, 2);//為鏈表添加一個結點
127     AddToTail(&pNode1, 3);//為鏈表添加一個結點
128     AddToTail(&pNode1, 4);//為鏈表添加一個結點
129     AddToTail(&pNode1, 5);//為鏈表添加一個結點
130     AddToTail(&pNode1, 6);//為鏈表添加一個結點
131     AddToTail(&pNode1, 7);//為鏈表添加一個結點
132     //打印鏈表
133     PrintList(pNode1);//打印
134     //反轉鏈表
135     ListNode* KthNode=FindKthToTail(pNode1,3);
136 
137     PrintListNode(KthNode);
138 
139     DestroyList(pNode1);
140     
141     return 0;
142 }