http://blog.csdn.net/ruizeng88/article/details/6700727
2011
面试中经常出现的编程题之一。
最直接的办法是先遍历一遍单链表,记下链表的节点数,然后再次遍历,直到到达节点数减去n的节点,返回结果。实际情况中若链表数目很多而n相对不大,这种方法需要大约两次遍历。更简单的实现方法是采用双指针。一个指针先从链表头开始步进n步,然后另一个指针从头开始,两个指针一同步进直到达到链表尾。这是第二个指针所指的节点即为链表的倒是第n个节点。实现代码如下:
1.n大于节点数目
2.参数n为0或者负数
3.参数head为空指针
双链表方法可以实现很多问题的解答,还有一个例子是求单链表是否有环。这时可以使用两个链表,一个步进一步,一个步进两部,如果有环两链表就会相遇。
联系客服