数据结构-单链表进阶之快慢指针原理（快速查找法）

面试题：快速找到未知长度单链表的中间节点？

这个问题的解决方法分为普通方法和高级方法。

1.普通方法即我们大家都能一下子想到的，首先遍历一遍获取总长度L，然后再次遍历循环至L/2即可；时间复杂度为：

O(L+L/2)=O(3/2L)

代码简单实现：

typedef struct {int data;LNode *next; }LNode,*LinkList;/* function:普通方法 首先遍历一遍获取总长度L，然后再次遍历循环至L/2即可 */ LNode *getElement(LinkList L) {if (L == NULL) {return NULL;}int i = 1;LNode *p = L->next;while (p!=NULL){p = p->next;i++;}int j = 1;int mid = i / 2;LNode *midNode = L->next;while (j<mid){midNode = midNode->next;}return midNode; }

2.高级方法：快慢指针法，设置2个指针*faster，*mid都指向单链表的头节点，其中faster移动的速度为mid的2倍，当faster移动到末尾，mid即在中间位置了，以下是简单实现:

/* function:快速查找未知长度单链表中间节点 快慢指针法 */ LNode *fasterGetElement(LinkList L) {LNode *mid, *faster;mid = L->next;faster = L->next;while (faster!=NULL){mid = mid->next;//faster = faster->next->nextfaster = faster->next;faster = faster->next;}return mid; }

转载于:https://www.cnblogs.com/babac/p/9028466.html

总结

以上是生活随笔为你收集整理的数据结构-单链表进阶之快慢指针原理（快速查找法）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。