有关单向链表的题目

1、编码的关键是思路,思路不对,不可能编出正确的代码。考虑下面两个关于单向链表的题目:

2、单向链表,如何判断是否构成环形?

  a、思路一:常规做法,建个集合,遍历单向链表,集合没有包含元素,添加进去集合,集合包含元素直接返回true,跳出遍历,返回false。

  b、思路二:使用快慢指针,建立两个节点,n1从head开始,n2从head->next开始,while(n1 && n2),n1每次走一步,n2每次走两步。如果n2先走到null,说明没有环。如果n1==n2,说明有环,n2又从后面追上来。

3、对于单向链表,查找倒数第K个节点。

  a、思路一:先计算节点个数,倒数第K个,就是正数Count-K-1

  b、建立两个节点,n1,n2,n1先移动K个单位,然后n1,n2同时向后移动,n1移动到null,n2就是倒数第K个。

原文地址:https://www.cnblogs.com/nzbbody/p/3558336.html