1、在O(1)时间删除链表节点
题目描述：给定链表的头指针和一个节点指针，在O(1)时间删除该节点。
思路分析：用下一个节点的数据覆盖要删除的节点，然后直接删除待删除节点的下一个节点就好了。（狸猫换太子）
如果节点是尾节点时就行不通
void deleteRandomnode(Node *cur){ //assert(cur != NULL); //assert(cur->next != NULL); Node * cur_Next = cur->next; cur->data = cur->next->data; cur->next = cur->next->next; //delete cur_next; //free(cur_Next) }
２、单链表的转置
题目描述：输入一个单向链表，输出逆序反转后的链表
思路分析：利用next 和 prev 来将下一个节点指向上个一节点。(实现转置)
Node * reverseByloop(Node *head){ if(head == NULL || head->next == NULL){ return head; } Node * prev, * next; prev = next = NULL; while(head != NULL){ next = head->next; head->next = prev; prev = head; head = next; }
return prev; }
３、求链表倒数第k个节点
问题描述：输入一个单向链表，输出该链表中倒数第k个节点，链表的倒数第0个节点为链表的尾节点（无非就是fast是先走k步还是k-1步）
思路分析：用快慢指针,快指针先走k步然后在和慢指针一起走，快指针走到尾节点，慢指针的位置就刚好是倒数第k个节点。
Node * theKthNode(Node *head, int k){ if (k < 0) return NULL; Node * slow, *fast; slow = fast = head; int i = k; while(i != 0 && fast != NULL) fast = fast->next; // less then k linked list. if(i > 0) return NULL; while(fast != NULL){ fast = fast->next; slow = slow->next; } return slow; }
４、求链表的中间节点
问题描述：如果长度为偶数，返回中间两个节点其中一个，为奇数就返回中间节点。
思路分析：这个也用快慢指针，快指针一次跳两个节点，满指针一次一个节点，等快指针指向尾节点的时候，慢指针就在中间节点上。
Node * theIntermediatenode(Node *head){ if(head == NULL){ return NULL; } Node * slow, *fast; slow = fast = head; while(fast != NULL && fast->next != NULL){ fast = fast->next->next; slow = slow->next; } return slow; }
如果偶数节点数要返回后面那个中心节点的话，可以if(fast != NULL) return slow->next;
５、判断单链表是否存在环
问题描述：输入一个单链表，判断链表是否有环
思路分析：通过快慢指针（快指针两步，慢指针一步），如果存在环，那么他们一定会在环里相遇
_Bool hasCircle(Node *head, Node *meetnode){ Node *fast, *slow; fast = slow = head; while(fast != NULL && fast->next != NULL){ fast = fast->next->next; slow = slow->next; if(fast = slow){ meetnode = fast; return TURE; } } return FALSE; }
６、找到环的入口点
问题描述：输入一个单向链表，判断是否有环，如何找到环的入口点（就是尾节点的next节点）
思路分析：假设环内相遇节点是Ｍ，头节点到入口节点距离是ａ,r入口节点到Ｍ距离是ｂ。快慢节点相遇的时候，慢节点走了a+b = n,快节点走了a+b+k圈=2n。
如果慢节点再从头结点走n到达Ｍ,快节点再从Ｍ走k圈也将会到达Ｍ,那么快慢指针走的路不同的只有a那段，然后他们第一次相遇的节点就是入口节点。
Node * findLoopPort(Node *head){ //if head empty or single node,the ring does not exist. if(head == NULL || head->next == NULL){ return NULL; } Node *fast, *slow; fast = slow = head; if(hasCircle(head, slow)){ while(fast != slow){ fast = fast->next; slow = fast->next; } return fast; } //Non existence ring else return NULL; }
７、判断两个链表是否相交
问题描述：给出两个单链表的头指针判断链表是否相交
思路分析：两个链表一旦相交，接下来所有节点都是一样的，不论是到空也好还是环也好，判断不带环的节点直接看最后的尾节点是否相等。
_Bool isIntersect(Node *h1, Node *h2){ if(h1 == NULL || h2 == NULL){ return FALSE; } while(h1->next != NULL){ h1 = h1->next; } while(h2->next != NULL){ h2 = h2->next; } if(h1 == h2) return TURE; else return FALSE; }
８、两个链表相交的第一个公共节点
问题描述：如果两个单链表相交，求出他们的第一个公共节点
思路分析：既然相交节点后面的内容一致，那么算出两个链表的长度并算出差为ｇ然后让长的那个先走ｇ个节点，然后和短链表一起走，知道他们相等就是
第一个公共节点
int listLength(Node *head){ int len = 0;
while(head){ len++; head = head->next; } return len; } Node * findFirstIntersectNode(Node *h1, Node *h2){ int len1,len2; len1 = listLength(h1); len2 = listLength(h2); if(len1 > len2){ for(int i = 0; i < len1 - len2; i++) h1 = h1->next; } else{ for(int i = 0; i < len2 - len1; i++) h2 = h2->next; } while(h1 != NULL){ if(h1 == h2) return h1; h1 = h1->next; h2 = h2->next; } return NULL; }
９、链表有环，如何判断相交
问题描述：上面那个是针对无环的，这个是两个有环链表，判断是否相交
问题分析：如果两个带环链表相交那么他们拥有同一个环，环上任意一个节点都存在于两个链表上，因此可以判断一链表上相遇的那个节点在不在另外一个链表上。
_Bool isIntersectWithLoop(Node *h1, Node *h2){ Node *circlenode1, *circlenode2; if(!hasCircle(h1, circlenode1)) return FALSE; if(!hasCircle(h2, circlenode2)) return FALSE; Node *temp = circlenode2->next; while(temp != circlenode2){ if(temp == circlenode1) return TURE; temp = temp->next; } return FALSE; }
未完待续....