链表中倒数第k个结点－C++

分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程https://www.captainai.net/troubleshooter// 面试题22链表中倒数第k个结点 // 题目输入一个链表输出该链表中倒数第k个结点。为了符合大多数人的习惯 // 本题从1开始计数即链表的尾结点是倒数第1个结点。例如一个链表有6个结点 // 从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是 // 值为4的结点。 #include cstdio #include stdio.h #include stdlib.h struct ListNode { int m_nValue; ListNode *m_pNext; }; ListNode *CreateListNode(int value) { ListNode *pNode new ListNode(); pNode-m_nValue value; pNode-m_pNext nullptr; return pNode; } void ConnectListNodes(ListNode *pCurrent, ListNode *pNext) { if (pCurrent nullptr) { printf(Error to connect two nodes.\n); exit(1); } pCurrent-m_pNext pNext; } void PrintListNode(ListNode *pNode) { if (pNode nullptr) { printf(The node is nullptr\n); } else { printf(The key in node is %d.\n, pNode-m_nValue); } } void PrintList(ListNode *pHead) { printf(PrintList starts.\n); ListNode *pNode pHead; while (pNode ! nullptr) { printf(%d\t, pNode-m_nValue); pNode pNode-m_pNext; } printf(\nPrintList ends.\n); } void DestroyList(ListNode *pHead) { ListNode *pNode pHead; while (pNode ! nullptr) { pHead pHead-m_pNext; delete pNode; pNode pHead; } } void AddToTail(ListNode **pHead, int value) { ListNode *pNew new ListNode(); pNew-m_nValue value; pNew-m_pNext nullptr; if (*pHead nullptr) { *pHead pNew; } else { ListNode *pNode *pHead; while (pNode-m_pNext ! nullptr) pNode pNode-m_pNext; pNode-m_pNext pNew; } } void RemoveNode(ListNode **pHead, int value) { if (pHead nullptr || *pHead nullptr) return; ListNode *pToBeDeleted nullptr; if ((*pHead)-m_nValue value) { pToBeDeleted *pHead; *pHead (*pHead)-m_pNext; } else { ListNode *pNode *pHead; while (pNode-m_pNext ! nullptr pNode-m_pNext-m_nValue ! value) pNode pNode-m_pNext; if (pNode-m_pNext ! nullptr pNode-m_pNext-m_nValue value) { pToBeDeleted pNode-m_pNext; pNode-m_pNext pNode-m_pNext-m_pNext; } } if (pToBeDeleted ! nullptr) { delete pToBeDeleted; pToBeDeleted nullptr; } } ListNode *FindKthToTail(ListNode *pListHead, unsigned int k) { if (pListHead nullptr || k 0) return nullptr; ListNode *pAhead pListHead; ListNode *pBehind nullptr; for (unsigned int i 0; i k - 1; i) { if (pAhead-m_pNext ! nullptr) pAhead pAhead-m_pNext; else { return nullptr; } } pBehind pListHead; while (pAhead-m_pNext ! nullptr) { pAhead pAhead-m_pNext; pBehind pBehind-m_pNext; } return pBehind; } // 测试代码 // 测试要找的结点在链表中间 void Test1() { printf(Test1 starts:\n); ListNode *pNode1 CreateListNode(1); ListNode *pNode2 CreateListNode(2); ListNode *pNode3 CreateListNode(3); ListNode *pNode4 CreateListNode(4); ListNode *pNode5 CreateListNode(5); ConnectListNodes(pNode1, pNode2); ConnectListNodes(pNode2, pNode3); ConnectListNodes(pNode3, pNode4); ConnectListNodes(pNode4, pNode5); printf(expected result: 4.\n); ListNode *pNode FindKthToTail(pNode1, 2); PrintListNode(pNode); DestroyList(pNode1); } // 测试要找的结点是链表的尾结点 void Test2() { printf(Test2 starts:\n); ListNode *pNode1 CreateListNode(1); ListNode *pNode2 CreateListNode(2); ListNode *pNode3 CreateListNode(3); ListNode *pNode4 CreateListNode(4); ListNode *pNode5 CreateListNode(5); ConnectListNodes(pNode1, pNode2); ConnectListNodes(pNode2, pNode3); ConnectListNodes(pNode3, pNode4); ConnectListNodes(pNode4, pNode5); printf(expected result: 5.\n); ListNode *pNode FindKthToTail(pNode1, 1); PrintListNode(pNode); DestroyList(pNode1); } // 测试要找的结点是链表的头结点 void Test3() { printf(Test3 starts:\n); ListNode *pNode1 CreateListNode(1); ListNode *pNode2 CreateListNode(2); ListNode *pNode3 CreateListNode(3); ListNode *pNode4 CreateListNode(4); ListNode *pNode5 CreateListNode(5); ConnectListNodes(pNode1, pNode2); ConnectListNodes(pNode2, pNode3); ConnectListNodes(pNode3, pNode4); ConnectListNodes(pNode4, pNode5); printf(expected result: 1.\n); ListNode *pNode FindKthToTail(pNode1, 5); PrintListNode(pNode); DestroyList(pNode1); } // 测试空链表 void Test4() { printf(Test4 starts:\n); printf(expected result: nullptr.\n); ListNode *pNode FindKthToTail(nullptr, 100); PrintListNode(pNode); } // 测试输入的第二个参数大于链表的结点总数 void Test5() { printf(Test5 starts:\n); ListNode *pNode1 CreateListNode(1); ListNode *pNode2 CreateListNode(2); ListNode *pNode3 CreateListNode(3); ListNode *pNode4 CreateListNode(4); ListNode *pNode5 CreateListNode(5); ConnectListNodes(pNode1, pNode2); ConnectListNodes(pNode2, pNode3); ConnectListNodes(pNode3, pNode4); ConnectListNodes(pNode4, pNode5); printf(expected result: nullptr.\n); ListNode *pNode FindKthToTail(pNode1, 6); PrintListNode(pNode); DestroyList(pNode1); } // 测试输入的第二个参数为0 void Test6() { printf(Test6 starts:\n); ListNode *pNode1 CreateListNode(1); ListNode *pNode2 CreateListNode(2); ListNode *pNode3 CreateListNode(3); ListNode *pNode4 CreateListNode(4); ListNode *pNode5 CreateListNode(5); ConnectListNodes(pNode1, pNode2); ConnectListNodes(pNode2, pNode3); ConnectListNodes(pNode3, pNode4); ConnectListNodes(pNode4, pNode5); printf(expected result: nullptr.\n); ListNode *pNode FindKthToTail(pNode1, 0); PrintListNode(pNode); DestroyList(pNode1); } int main(int argc, char *argv[]) { Test1(); Test2(); Test3(); Test4(); Test5(); Test6(); return 0; } // ------ Output ------ /* Test1 starts: expected result: 4. The key in node is 4. Test2 starts: expected result: 5. The key in node is 5. Test3 starts: expected result: 1. The key in node is 1. Test4 starts: expected result: nullptr. The node is nullptr Test5 starts: expected result: nullptr. The node is nullptr Test6 starts: expected result: nullptr. The node is nullptr */