每次做算法基础练习就意识到自己有多笨，还是做一下笔记，时常看一看，能开拓一下思路，希望能积少成多。
- 链表原地反转：
思路： 边遍历，边反向改next指针- pre -> current -> next
- pre <- current next
- 将 pre 赋值为 current， current 赋值为 next， next 赋值为next.next ，相当于整体后移一位。
- 重复 2的操作，每次反向改一次next指向。
class Node : NSObject {
var value : NSObject;
var next : Node?;
init(value:NSObject) {
self.value = value;
}
}
//链表原地反转
func reverse(head : Node?) {
if (head == nil || head?.next==nil) {
return;
}
var pre : Node? = nil;
var current :Node = head!;
var next : Node? = head!.next!;
while head!.next != nil {
current.next = pre;
pre = current;
current = next!;
next = current.next;
}
}
2.链表成环判断
/*
如果链表成环，只能是O型环，或者6形状环。 如果是O型的环，一个指针p站在原地不动，一个指针q出去跑一圈，一定等遇到q，但如果是6形状的环，前种方法就不行了。因此，p和q就都要出去跑圈，如果，让q跑快一点，p跑慢一点，如果链表成环的话，无论是O型状的，还是6型状的，q肯定会在某个时间节点，比q多跑一圈，而追上p，及p和q从header出发后，首次相遇。
*/
func hasCircle(head : Node?) -> Bool {
if (head == nil || head?.next == nil) {return false};
var current : Node? = head;
var another : Node? = head!.next;
while current?.next != nil {
if current! === another! {
return true;
} else {
current = current?.next;
another = another?.next?.next;//让一个点跑快一点。。。。
}
}
return false;
}
//链表相交
/*
链表的相交，一定是Y型相交，既然是Y型相交，必定有相同的trail，如果有相通的trail，则相交。相交后找交点 ，遍历两个链表的同时，记录长度，max链表长-min链表长 = n，长链表和短链表一起向下找相同元素，长链表从第n个节点开始，找到第一个相同的节点。
*/
func findSameNode (head1:Node?, head2:Node?) -> Node? {
if head1 == nil || head2 == nil {return nil}
var length1 : Int = 1;
var length2 : Int = 1;
var p : Node = head1!;
var q : Node = head2!;
while p.next != nil || q.next != nil {
if (p.next != nil) {
length1 += 1;
p = p.next!;
}
if (q.next != nil) {
length2 += 1;
q = q.next!;
}
}
if (p === q) {
//有共同的尾部
let sub : Int = abs(length1 - length2);
var maxList : Node = length1>length2 ? head1! : head2!;
var minList : Node = length1>length2 ? head2! : head1!;
for _ in 1...sub {
maxList = maxList.next!;
}
for _ in 1...max(length2, length1) {
if (maxList === minList) {
return maxList;
} else {
if maxList.next != nil && minList.next != nil {
maxList = maxList.next!;
minList = minList.next!;
} else {
return nil;
}
}
}
} else {
//没有共同的尾部，没有相交
return nil;
}
return nil;
}
//给定链表的头指针和一个节点指针，在O(1)时间删除该节点
/*
主要思想都是「狸猫换太子」 将给定节点的值改为，该节点next的值，将该节点next指针设为next的next节点。
*/
//求链表倒数第k个节点
/* 题目描述：输入一个单向链表，输出该链表中倒数第k个节点，链表的倒数第0个节点为链表的尾指针。
分析：设置两个指针 p1、p2，首先 p1 和 p2 都指向 head，然后 p2 向前走 k 步，这样 p1 和 p2 之间就间隔 k 个节点，最后 p1 和 p2 同时向前移动，直至 p2 走到链表末尾。
*/
//求链表的中间节点,要求时间复杂度是O(n),遍历不得超过一次。
/*
受上面一题的启发，应该也可以只用两个指针同时遍历列表，如果指针p，指针q，同时从起点出发，如果q的速度是p的2倍的时候，那么当q到达终点的时候，p刚好才走到全程的一半。
及 q在遍历时每次走两步，q = q.next.next ，p走一步，p = p.next
*/
//找到环的入口点
//输入一个单向链表，判断链表是否有环。如果链表存在环，如何找到环的入口点？
/*
又是环的问题，环的问题一般都可转化到数学里的，同向运动的相遇问题，p，和q，同时出发，如果q比p跑得快，那么总有一时间点，q会比p跑一圈而相遇。那么可以设p的速度是1⃣️，q的速度是2⃣️，在遍历链表的过程中记录p走过的路程，及节点数n，q走过的路程及是2n。 此时可以得处环状的长度是n。得到环的长度后，可以进入第二步，找环的入口。
让p，q都回到链表的初始位置，q先行n步，然后，p，q同时以1⃣️的速度向下一个节点移动，直到，p和q相遇，此时p，q所处的位置即环的入口。
*/
//8. 扩展：链表有环，如何判断相交
//题目描述：上面的问题都是针对链表无环的，那么如果现在，链表是有环的呢?上面的方法还同样有效么?
/*
此时可以设想一下，如果两个链表相交，且两个链表相交，那么两个链表一定共同一个环。那么第一步，按照上述方法，假设链表A，B
1⃣️：利用p，q指针找到链表A的环入口 E1，和环的长度n。由于A和B同环，B的环长也是n，记录链表A的全长。
2⃣️：让p，q同时都在B链表的head处，让q先行n步，若在N步，然后p，q同时，同速度向后移近，在p，q相遇前，若q能等于E1，那么A、B链表相交于环部。否则，p，q，相遇时，记录链表B的长度。进入第3⃣️步
3⃣️：计算链表A，B的长度差 X，让p，q分别从A，B链表的head出发，长链表的指针先行X步，然后p，q同时移动，在p到达E1点前，如果p==q，那么AB相交于环外节点，否则无交点。
*/
