1、倒转单链表
非递归法
- struct Node
- {
- int data;
- Node * next;
- }
- void reverse(Node*& head) {
- if (head == NULL) {
- return;
- }
- Node * pre, * cur, * nxt;
- pre = head;
- cur = head -> next;
- while (cur != NULL) {
- pre = cur -> next;
- pre = cur;
- cur = nxt;
- nxt = nxt -> next;
- }
- head -> next = NULL;
- head = pre;
- }
递归法
- Node * reverse(Node * node, Node *&head)
- {
- if (node == NULL || node -> next == NULL) {
- head = node;
- return;
- }
- else {
- Node * nxt = reverse(node -> next, head)
- node = nxt -> next;
- return node;
- }
- }
- 最后要将返回的node的next域设为NULL。
2、找出倒数第k个元素(或中间元素）：设置快慢指针
3、删除环状单链表的一个节点，只给定指向要删除节点的指针
思路：无法获取前一个指针，那么可删除下一个节点，交换当前节点和下一个节点的值即可
4、两个有序链表的合并
归并即可
5、判断单链表是否有环？环首？
是否有环：快慢指针，如果相遇，说明存在环
环首：可先求出环长。一个圆内的追及问题，两次相遇时慢指针走过的距离即环长；
此时假设慢指针已走了i步，则快指针已走了2i步；两个指针同时倒退i步的位置，慢指针退到链首，快指针退到i处，则从这两个位置起，指针各走i步既能在环内相遇。
于是可设置两个指针，一个在链首处，一个在i处，步长为1，第一次相遇的节点即为环首的位置。
6、如何判断两个链表是否交叉？如果找到交叉点？
思路同5
|