thinking1.py

#1-4题的原理和思路
'''
1_1.py 就地逆序
主要思路：在遍历链表的时候，修改当前节点的指针域的指向，让其指向它的前驱节点。
特别注意对链表収为结点的特殊处理。

对链表进行一次遍历，时间复杂度O(n)；常数个额外变量保存前驱后驱结点，时间复杂度O(1)。

1_2.py 递归法
主要思路：先逆序除第一个结点以外的子链表，接着把结点1添加到逆序的子链表的后面。
1->2->3->4->5->6->7   -->   1->7->6->5->4->3->2   -->   7->6->5->4->3->2->1
同理 逆序   2->3->4->5->6->7       3->4->5->6->7

对链表进行一次遍历，时间复杂度O(n)；缺点是：算法实现的难度较大，此外递归法不断调用自己，需要额外压栈和弹栈操作，性能下降。

1_3.py  插入法
主要思路：从链表的第二个结点开始，把遍历到的结点插入到头结点的后面，直到遍历结束。
head->1->2->3->4->5->6->7   遍历到2的时候,将其插入到头结点后，变为head->2->1  3->4->5->6->7

对单链表进行一次遍历，时间复杂度O(n),与方法一相比，不需要保存前驱节点的地址，与方法二相比，不需要递归地调用，效率更高。
'''


'''
2_1.py  顺序删除
主要思路：通过双重循环直接在链表上进行删除操作。
外层循环用一个指针从第一个结点开始遍历整个链表，内存循环用另外一个指针遍历其余结点，删除相同结点。

采用双重循环对链表进行遍历，时间复杂度O(n^2)；常数个额外的指针变量来保存当前遍历的结点、前驱结点和被删除的结点，空间复杂度O(1)。

2_2.py  递归法
主要思路：对于结点cur,首先递归地删除以cur.next为首的子链表中重复的结点，接着从以cur.next为首的子链表中找出与cur相同数据域的结点并删除。

本质上需要双重遍历，时间复杂度为O(n^2);由于递归法会增加许多额外的函数调用，因此理论上，该方法比方法一低。

空间换时间
通常情况下，为了降低时间复杂度，往往在条件允许的情况下，通过辅助空间来实现。
主要思路：
(1)建立一个HashSet，内容为已经遍历过的所有结点，并将其初始化为空。
(2)从头开始遍历链表中的所有结点，存在以下可能：
    1)结点在HashSet中，那么删除此节点，向后遍历；
    2)结点不在HashSet中，那么保留此结点，内容添加到HashSet中，继续向后遍历
'''


'''
整数相加法
主要思路：分别遍历两个链表，求出两个链表所代表的整数的值，然后把这两个整数进行相加，最后把它们的和用链表的形式表示出来。
优点：计算简单；缺点：当链表所代表的数很大的时候(超过Long的表示范围),就无法使用这种方法了。

3.py 链表相加法
主要思路：对链表中的结点直接进行相加操作，把相加的和存储到新的链表中对应的结点中，同时记录结点相加后的进位。
注意点：1)是否有进位；2)两个链表长度不同；3)最高位计算后仍有进位，需要增加新的结点，数据域为1。

需要对两个链表都进行遍历，时间复杂度为O(N);计算结果保存在一个新的链表中，空间复杂度也为O(N)。
'''

'''
4.py 中间结点逆序法
(1)首先找到链表的中间结点;(2)对链表的后半部分子链表进行逆序;(3)把链表的前半部分子链与逆序后的后半部分子链合并：各取一个结点合并。

查找链表的中间结点，时间复杂度为O(N)，逆序子链表的时间复杂度也为O(N),合并两个子链表的时间复杂度也为O(N),整体时间复杂度也为O(N)；
常数个额外指针变量，空间复杂度O(1)。
'''