thinking2.py

#5-8题的思路和结果
'''
顺序遍历两遍法
主要思路:首先遍历一遍单链表，求出整个单链表的长度n,然后把求倒数第k个元素转换为求顺数n-k个元素，再去遍历一次单链表，但需要遍历两次。

5.py    快慢指针法
主要思路:设置两个指针，让其中一个指针比另外一个指针先前移k步，然后两个指针同时往前移动。

只需要对链表进行一次遍历，时间复杂度为O(N);只需常量个指针变量来保存结点的地址信息，空间复杂度为O(1)。
'''

'''
蛮力法:
定义一个HashSet用来存放结点的引用，并将其初始化为空，从链表的头结点开始往后遍历，每遍历一个结点就判断HashSet中是否有这个结点的引用。
如果没有，说明这个结点是第一次访问，那么将这个结点的引用添加到HashSet中去；
如果在HashSet中找到了相同的结点，那么形成了环。
时间复杂度O(N);空间复杂度也为O(N)。

6.py    快慢指针遍历法
主要思路：定义两个指针fast、slow，初始值指向链表头，分别每次前进两、一次，如果快指针等于慢指针，证明链表带环。

引申：如果链表存在环，那么如何找出环的入口点？
当快慢指针相遇，slow指针还未遍历完，fast指针在环内循环了n圈。
假设slow指针走了s步，fast指针走了2s步，假设环长为r，则
2s = s + nr  -->   s = nr

设整个链表长为L，入口环与相遇点距离为x，起点到环入口的距离为a，则
a + x = nr   -> a + x = (n-1)r + L -a  -> a = (n-1)r + (L-a-x)
L-a-x为相遇点到环入口点的距离
于是从链表头与相遇点分别设一个指针，每次走一步，两个指针必然相遇，且相遇点为环入口点

只需要对链表进行一次遍历，时间复杂度O(N);只需要几个常量指针保存结点信息，空间复杂度O(1)。
'''

'''
交换值法
交换两个结点的数据域，不需要重新调整链表的结构。

7.py    就地逆序
主要思路：通过调整结点指针域的指向来直接调换相邻的两个结点。

只需要对链表进行一次遍历，时间复杂度为O(N)；只需要几个指针变量来保存结点的地址信息，空间复杂度为O(1)。
'''

'''
8.py 翻转
主要思路：首先把前K个结点看成一个字链表，采用前面介绍过的方法进行翻转，把翻转后的子链表链接到头结点后面，然后把接下来的K个结点完成相同操作。

(1)首先设置pre指向头结点，然后begin指向链表第一个结点，找到从begin开始第K个结点end
(2)为了使用reverse，需要分离需要翻转的子链表，end.next = None，end指向的结点，用p指针来记录
(3)从begin到end是一个独立的子链表，reverse(begin)
(4)翻转后，链表头为end，链表尾为begin， pre.next = end
(5)把链表中剩余的还未完成翻转的子链表链接到已经完成翻转的子链表后面，注意个数不足k的部分
(6)pre指向完成翻转的链表的最后一个结点
(7)让begin指针指向下一个需要被翻转的子链表的第一个结点

只需对链表进行一次遍历，时间复杂度为O(N)，只需要几个指针变量来保存结点地址信息，空间复杂度为O(1)。
'''