1.倒序打印单项链表
- 存入数组然后倒着输出
- 一直标记最后一位的前一位
- 递归
递归代码：
void func(Node* pHead) { if(pHead == NULL) return ; func(pHead->next); printf("%d ",pHead->val); }
2.倒置链表
- 以中间为分界点，置换相对位置
- 递归时放入新链表
- 指针数组装对应节点地址
- 用三个指针实现倒置
三个指针的代码:
Node* Reverse(Node* node) { Node* pre = node; Node* p = node->next; Node* pnxt = p->next; node->next = NULL; while(pnxt != NULL) { p->next = pre; pre = p; p = pnxt; pnxt = pnxt->next; } p->next = pre; return p; }
3.Y形链表，即普通单项交叉链表
求交叉节点？
- A的每个节点和B的所有节点比较
- 存在数组里
- 压入栈里（两个栈每次弹出一个然后比较）
- 计算两个链表的长度，A链表长m，B链表长n，m>n,A链表从m-n处开始，B链表从头开始，判断两个链表相同的节点即为交叉节点
4.判断链表是否有环 6形
找到环的入口节点？
快慢指针：一个指针以1倍速度遍历链表，另一个以2倍速度遍历链表，它们可以相遇，则链表有环。
标记相遇节点，再走一圈则得出环的长度l,链表头结点标记为p1，p2。p1先走l步，然后再和p2一起走，当p1,p2相等时则为入口点。
我的理解：假设链表总长度L，p1先走l步，则剩下的距离为L-l，即回到入口结点。p2从头结点到环的入口节点的距离为L-l。如果二者同时走则相遇的点为入口节点。