首页 > 代码库 > 链表算法总结
链表算法总结
代码写过可能就会忘了，但是如果思路还在的话，我们就能够顺着思路去写代码，所以此处侧重于对思路的总结；此处，我主要作为搬运工然后再加入自己的一些理解。
1：题目描述：给定链表的头指针和一个节点指针，在O(1)时间删除该节点。[Google面试题]
思路： 要删除链表节点我们一般要找到的节点的前驱节点： 而此题目给了我们一个当前的节点指针，显然要在O(1)的时间删除该节点， 所以我们只能够把这个节点指针当做前驱节点，因此要删除的就是后续节点了。 可是我们目的是为了删除当前指针所指的节点。
解决的方法： 把后续节点的值赋值给当前节点，然后删除后续节点就可以了。
1 //O(1)时间删除链表节点，从无头单链表中删除节点 2 void deleteRandomNode(Node *cur) 3 { 4 assert(cur != NULL); 5 assert(cur->next != NULL); //不能是尾节点 6 Node* pNext = cur->next; 7 cur->data = http://www.mamicode.com/pNext->data; 8 cur->next = pNext->next; 9 delete pNext;10 }
题目二：单链表的反转
基本的单链表的翻转有三种种方式: 其一是非递归方式（直接遍历一遍） 其二就是利用头插法将单链表反转了， 其三就是利用递归的方式进行反转了。
方式1：
思路：总体思路很简单就是在遍历单链表的过程中把第一个节点的指针置空， 把第二个节点的指向第一个节点， 把第三个节点指向第二个节点，依此类推（此处需要定义连个指针， 一个指向当前的节点的指针 Node* cur 一个 指向当前节点的前驱节点的指针 Node* pre )。
注意点也是比较重要的点就是： 我们在把第二个节点指向第一个节点的时候，或者把第三个节点指向第二个节点的时候， 链表会断掉，为了防止链表断掉，我们需要定义一个指针来记录当前节点的后续节点。(此处需要定义一个当前节点的后续节点： Node* next）每次操作完之后都会形成两个链表其中pre 指向 第一个链表的最后一个节点（之所以说是最后一个节点是因为我是根据原来的链表的位置对其进行描述，也可以说是新链表的第一个节点） head 指向第二个链表的第一个节点， 核心操作如下
1 Node* pre = NULL;2 Node* next = NULL;3 next = head->next;//为了防止在循环过程中我们把当前节点指向下一个节点的过程中链表断掉，定义一个next指针指向指向当前节点的下一个节点。 4 head->next = pre;5 pre = head;// 因为要遍历整个单链表所以 pre 和 head 都要跟上来其中处的head 指的是当前的节点。6 head = next;
以下为具体的代码：
//单链表的转置,遍历的方法Node* reverseByLoop(Node *head){ if(head == NULL || head->next == NULL) return head; Node *pre = NULL; Node *next = NULL; while(head != NULL) { next = head->next; head->next = pre; pre = head; head = next; } return pre;}
方法二：头插入法就是将单链表逐个取下来，在前面进行插入的方式，第一取节点下来在第一个位置， 第二个节点取下来插在第一个节点的前面，第三个节点取下来插入第二个节点的前面（也就是整体的前面）以此类推。具体的代码执行过程如下：
1 //每次从链表中取一个节点把它插入在链表的头部。实现链表的逆转 此处针对的是链表已经存在的情况 2 Node* ReverseByInsertF(Node* p) 3 { 4 Node* pre = NULL , *cur = p; 5 while(cur) 6 { 7 Node* next = cur->next;//此处是因为怕每一次取一个节点接在链表的前面时候断链所以先缓存要取下的节点的下一个节点 8 cur->next = pre; //每次将剩下的链表的第一个节点（即当前节点）取下接在每次经过反转的链表的第一个节点。 9 pre = cur; // 其中pre 指向的是反转之后的链表的第一个节点10 cur = next;11 }12 13 }
方法三： 采用递归的方式：
思路：在反转当前节点之前先反转后续的节点 具体的过程如下
1 //单链表的转置,递归方法 2 Node* reverseByRecursion(Node *head) 3 { 4 //第一个条件是判断异常，第二个条件是结束判断 5 if(head == NULL || head->next == NULL) 6 return head; 7 Node *newHead = reverseByRecursion(head->next); 8 head->next->next = head; 9 head->next = NULL;10 return newHead; //返回新链表的头指针11 }
链表算法总结