归档 2015年7月10日

题目描述：

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

题目大意：

给定一个链表，返回循环的起始节点。如果没有环，则返回空。

进一步思考：

你可以在不使用额外空间的条件下完成题目吗？

解题思路：

参考LeetCode Discuss（https://leetcode.com/discuss/16567/concise-solution-using-with-detailed-alogrithm-description）

1). 使用快慢指针法，若链表中有环，可以得到两指针的交点M

2). 记链表的头节点为H，环的起点为E ...

题目描述：

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

题目大意：

给定一个单链表，判断它是否是回文。

进一步思考：

你可以在O(n)时间复杂度和O(1)空间复杂度完成吗？

解题思路：

1). 使用快慢指针寻找链表中点

2). 将链表的后半部分就地逆置，然后比对前后两半的元素是否一致

3). 恢复原始链表的结构（可选）

Python代码：

# Definition for singly-linked ...