本文共 1533 字，大约阅读时间需要 5 分钟。
题目：
输入一个链表，输出该链表的第K个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。
链表的定义如下：
struct ListNode{ int value; ListNode *next; ListNode(int a){ value = a; next = NULL; }};思路： 这题比较简单，先遍历链表一遍，获得链表大小。在从头开始，找到对应结点即可。
时间复杂度：O（n）
鲁棒性：
如果链表大小size小于K时，要进行处理。
如果头结点为空或k小于1也需要处理。
如果只能遍历链表一遍呢？
这种解法以前见到过，可是看到这个题目时，没有想起来。方法是用两个指针，第一个指针走K-1步后，第二个指针开始走，当第一个指针到达最后一个结点时，第二个指针便指向了倒数第K个结点。#include相关题目： 1.求链表的中间结点。如果链表中结点总数为奇数，返回中间结点，如果为偶数，返回中间两个的任意一个。#include #include #include #include using namespace std;struct ListNode{ int value; ListNode *next; ListNode(int a){ value = a; next = NULL; }};ListNode *findNode(ListNode *head, int targetBackIndex){ if (head == NULL || targetBackIndex == 0) return NULL; ListNode *front = head, *rear = head; int count = 0; while (front->next != NULL) { if (count >= targetBackIndex - 1) { rear = rear->next; } front = front->next; ++count; } if (count < targetBackIndex-1) throw new std::exception("invalid input"); return rear;}int main(){ ListNode *a1 = new ListNode(1); ListNode *a2 = new ListNode(2); ListNode *a3 = new ListNode(3); ListNode *a4 = new ListNode(4); ListNode *a5 = new ListNode(5); a1->next = a2; a2->next = a3; a3->next = a4; a4->next = a5; ListNode *re = findNode(a1, 0); cout << re->value << endl; return 0;}
额，同样两个指针，一个每次走两步，一个每次走一步，这样当第一个走到最后时，第二个刚好到中间。
2.判断一个单向链表是否形成了环形结构。
环形链表不一定是首位相连，也可能在中间形成环状，且环状会一直循环，除非有结束标志的结点。
所以，可以指定两个指针，一个每次走两步，一个每次走一步，如果走的快的追上了走的慢的（相等），则说明是环形结构，如果走的快的走到了最后（空），则说明不是环形结构。
转载地址：http://papmi.baihongyu.com/