链表中倒数第k个结点
思路:设置两个指针,一个慢指针pSlow,一个快指针pFast,快指针先走k-1步,接着两个指针同时走,当快指针到达链表的尾部,慢指针恰好指向倒数第k个结点。
特殊情况:当k大于链表长度,则返回头结点。
代码:
#include "stdafx.h" #include <iostream> using namespace std; struct ListNode { int m_nValue; ListNode *m_pNext; }; ListNode *FindKthToTail(ListNode *pHead, int k) { if (pHead == NULL || k == 0) { return NULL; } ListNode *pSlow = pHead; ListNode *pFast = pHead; int i = 1; while (i < k) { pFast = pFast->m_pNext; if (pFast == NULL) { cout << "k = " << k << "大于链表长度!" << endl; break; } i++; } if (pFast != NULL) { while (pFast->m_pNext != NULL) { pSlow = pSlow->m_pNext; pFast = pFast->m_pNext; } } return pSlow; } //创建一个链表,输入从头到尾结点的值,输入-1表示结束 void CreateList(ListNode *& pHead) { ListNode *pListNode = NULL; ListNode *pCurLastNode = NULL; bool isHead = true; while (1) { if (isHead) { pHead = new ListNode(); cin >> pHead->m_nValue; pHead->m_pNext = NULL; isHead = false; pCurLastNode = pHead; } else { pListNode = new ListNode(); cin >> pListNode->m_nValue; if (pListNode->m_nValue == -1) { break; } pListNode->m_pNext = NULL; pCurLastNode->m_pNext = pListNode; pCurLastNode = pListNode; } } } //从头到尾打印链表 void PrintList(ListNode *&pHead) { if (pHead != NULL) { ListNode *pCur = pHead; while (pCur != NULL) { cout << pCur->m_nValue << " "; pCur = pCur->m_pNext; } cout << endl; } else { cout << "链表为空!" << endl; } } int _tmain(int argc, _TCHAR* argv[]) { ListNode *pListHead = NULL; CreateList(pListHead); PrintList(pListHead); ListNode *pKthNodeToTail = FindKthToTail(pListHead, 6); cout << pKthNodeToTail->m_nValue << endl; return 0; } #include "stdafx.h" #include <iostream> using namespace std; struct ListNode { int m_nValue; ListNode *m_pNext; }; ListNode *FindKthToTail(ListNode *pHead, int k) { if (pHead == NULL || k == 0) { return NULL; } ListNode *pSlow = pHead; ListNode *pFast = pHead; int i = 1; while (i < k) { pFast = pFast->m_pNext; if (pFast == NULL) { cout << "k = " << k << "大于链表长度!" << endl; break; } i++; } if (pFast != NULL) { while (pFast->m_pNext != NULL) { pSlow = pSlow->m_pNext; pFast = pFast->m_pNext; } } return pSlow; } //创建一个链表,输入从头到尾结点的值,输入-1表示结束 void CreateList(ListNode *& pHead) { ListNode *pListNode = NULL; ListNode *pCurLastNode = NULL; bool isHead = true; while (1) { if (isHead) { pHead = new ListNode(); cin >> pHead->m_nValue; pHead->m_pNext = NULL; isHead = false; pCurLastNode = pHead; } else { pListNode = new ListNode(); cin >> pListNode->m_nValue; if (pListNode->m_nValue == -1) { break; } pListNode->m_pNext = NULL; pCurLastNode->m_pNext = pListNode; pCurLastNode = pListNode; } } } //从头到尾打印链表 void PrintList(ListNode *&pHead) { if (pHead != NULL) { ListNode *pCur = pHead; while (pCur != NULL) { cout << pCur->m_nValue << " "; pCur = pCur->m_pNext; } cout << endl; } else { cout << "链表为空!" << endl; } } int _tmain(int argc, _TCHAR* argv[]) { ListNode *pListHead = NULL; CreateList(pListHead); PrintList(pListHead); ListNode *pKthNodeToTail = FindKthToTail(pListHead, 6); cout << pKthNodeToTail->m_nValue << endl; return 0; }
补充:软件开发 , C++ ,