做网站一年多少钱/网站建设流程图

1、前言

数组、链表、二叉树、动态规划、栈与队列是面试中常考的知识点，而在这几个知识点中，链表偏基础，但由于涉及指针的操作，但是却很能考察学生的编程功底，因此在这里总结一下二叉树常考的问题，包括：
（1）从尾到头输出链表；
（2）在O(1)时间内删除链表节点；
（3）链表中的倒数第K个节点；
（4）两个链表的第一个公共节点；
（5）反转链表；
（6）合并两个有序的链表；
（7）复杂链表的复制；
（8）判断环形链表中是否有环；
（9）找到环形链表环的入口；
（10）求环形链表环的长度；

2、链表中的常见问题

（1）从尾到头输出链表

基本思路：由于是单向链表，所以只能从头到尾进行遍历，要想从尾到头输出链表，一种可行的方法是在从头到尾遍历的时候，将每个遍历节点的值压入栈中。遍历完后，将栈中的元素一一弹出，即实现了从尾到头输出链表。

代码实现：

def TailtoHeadPrint(pHeadNode):stack = []pNode = pHeadNode.nexwhile pNode != None:stack.append(pNode.val)pNode = pNode.nexwhile len(stack) != 0:print(stack[-1])stack.pop()

（2）在O(1)时间内删除链表节点
基本思路：在单向链表中删除一个节点有两种方法：
（1）从头开始遍历链表，找到要删除节点的前一个节点，然后将前一个节点的next设置为要删除节点的next，这种方法的时间复杂度为O(n)
（2）通过要删除节点的next找到其下一个节点，然后将下一个节点的内容复制覆盖要删除的节点，再将下一个节点删除。
方法2有很多问题需要注意，1）如果要删除的节点是尾节点，由于它没有下一个节点，所以还需要从头开始遍历；2）如果链表中只有一个节点（既是头节点也是尾节点），直接删除该节点；

代码实现：

def DeleteNode(pHeadNode,node):if node.nex != None:node_next = node.nexnode.val = node_next.valnode.nex = node_next.nexdel node_nextelse:pNode = pHeadNodewhile pNode.nex != node:pNode = pNode.nexpNode.nex = Nonedel node

（3）链表的倒数第K个节点

基本思想：可以使用两个指针p1、p2，从头节点开始，p1先走K个节点，然后p1、p2一起走，当p1到达尾节点时，p1指向的即为倒数第K个节点。

注意以下边界条件：
1）当链表长度小于K的时候，倒数第K个节点不存在，返回空；
2）当链表为空时，倒数第K个节点也不存在，返回空

代码实现：

def ReciprocalkNode(pHeadNode,K):length = 0pNode = pHeadNode.nexwhile pNode != None:length += 1pNode = pNode.nexif length < K or pHeadNode.nex == None:return NonepNode1 = pHeadNodepNode2 = pHeadNodei = 0while i < K - 1:pNode1 = pNode1.nexi += 1while pNode1.nex != None:pNode2 = pNode2.nexpNode1 = pNode1.nexreturn pNode2

（4）两个链表的第一个公共节点

基本思路：由于是单链表，当两个链表A、B存在公共节点时，两个链表公共节点之后的所有节点都相同，即形成一个开口向左的"Y"字形，因此，我们可以使用两个指针p1、p2，p1指向链表A，p2指向链表B，假设链表A的比链表B长N个节点，则p1现在链表A上先走N个节点，然后p1、p2分别在链表A、B上同时走，直到p1、p2指向相同的节点为止。

代码实现：

        
def CommonNode(pHeadNode1,pHeadNode2):if pHeadNode1.nex == None or pHeadNode2.nex == None:return NonepNode1 = pHeadNode1.nexpNode2 = pHeadNode2.nexlength1 = 0length2 = 0while pNode1 != None:length1 += 1pNode1 = pNode1.nexwhile pNode2 != None:length2 += 1pNode2 = pNode2.nexK = abs(length1 - length2)longLinkList = NoneshortLinkList = Noneif length1 > length2:longLinkList = pHeadNode1shortLinkList = pHeadNode2else:longLinkList = pHeadNode2shortLinkList = pHeadNode1i = 0while i < K:longLinkList = longLinkList.nexi += 1while longLinkList.val != shortLinkList.val:longLinkList = longLinkList.nexshortLinkList = shortLinkList.nexreturn longLinkList

（5）反转链表

基本思路：反转链表，就是不断地调整相邻两个节点的next指针，让后一个节点的next指针指向它的前一个节点。所以我们需要三个指针p1、p2、p3，p1指向相邻两个节点中的前一个节点，p2指向后一个节点，p3用于保存p2的下一个节点，以便下一次的迭代。
需要注意的边界条件是：
1）当链表为空或只有一个节点时，不需要调整指针；

代码实现：

def Reverse_LinkList(pHeadNode):if pHeadNode.nex == None or pHeadNode.nex.nex == None:return pHeadNodepNode1 = pHeadNode.nexpNode2 = pNode1.nexpNode1.nex = NonepNode3 = Nonenew_pHeadNode = Nonewhile pNode2 != None:pNode3 = pNode2.nexnew_pHeadNode = pNode2pNode2.nex = pNode1pNode1 = pNode2pNode2 = pNode3Reverse_pHeadNode = LinkNode()Reverse_pHeadNode.nex = new_pHeadNodereturn Reverse_pHeadNode

（6）合并两个有序的链表

基本思路：合并两个有序链表的思路与合并两个有序数组的思想是一样的。
1）我们设置三个指针p1、p2、p3，p1指向第一个有序链表，p2指向第二个有序链表，p3指向合并后的新链表；

2）如果p1指向的节点值小于p2指向的节点值，则将p1指向的节点链接到p3的末尾，然后再将p1，p3向后移动一个节点；

3）如果p1指向的节点值大于或等于p1指向的节点值，则将p2指向的节点值链接到p3的末尾，然后再将p2，p3同时向后移动一个节点；

4）如果剩余的是第一个链表，则将第一个链表剩下的所有节点链接到p3的末尾；否则将第二个链表剩下的所有节点链接到p3末尾。

代码实现：

def Merge_LinkList(pHeadNode1,pHeadNode2):pNode1 = pHeadNode1.nexpNode2 = pHeadNode2.nexMerge_pHeadNode = LinkNode()pNode3 = Merge_pHeadNodewhile pNode1 != None and pNode2 != None:if pNode1.val < pNode2.val:pNode3.nex = pNode1pNode1 = pNode1.nexpNode3 = pNode3.nexelse:pNode3.nex = pNode2pNode2 = pNode2.nexpNode3 = pNode3.nexif pNode1 != None:pNode3.nex = pNode1if pNode2 != None:pNode3.nex = pNode2return Merge_pHeadNode

（7）复杂链表的复制
在复杂链表中，每个节点除了有一个指针next指向下一个节点，还有一个指针sib指向链表中任意节点或者NULL。
基本思路：要想实现链表的复杂链表的复制，有两种方法，

第一种方法先根据nex指针复制出一个新的链表，然后再复制新链表中每个节点的sib指针。

第二种方法是，
1）将复杂链表中的每个节点进行都复制，然后链接到被复制节点的后面，使得原链表扩充为原来2倍长度的新链表；

2）接着设置复制节点的sib指针，由于复制节点node’处于被复制节点node的后面，所以node’.sib 刚好等于node.sib的下一个节点，即node’.sib = node.sib.next；

3）最后将新链表拆成两个链表。

代码实现：

def Copy_ComplexLinkList(pHeadNode):pNode = pHeadNode.nexwhile pNode != None:copy_node = ComplexLinkNode()copy_node.val = pNode.valcopy_node.nex = pNode.nexpNode.nex = copy_nodepNode = copy_node.nexpNode1 = pHeadNode.nexwhile pNode1 != None:if pNode1.sib != None:pNode1.nex.sib = pNode1.sib.nexpNode1 = pNode1.nex.nexpNode2 = pHeadNode.nexcopy_pHeadNode = ComplexLinkNode()pNode3 = copy_pHeadNodewhile pNode2 != None:pNode3.nex = pNode2.nexpNode3 = pNode3.nexpNode2 = pNode2.nex.nexreturn copy_pHeadNode

(8) 判断环形链表是否有环
基本思路： 使用快慢指针fast和slow，fast初始指向head->next->next，slow指向head，当slow和fast都不为空，且slow不等于fast时，fast每次走两步，slow走一步，如果有环，则它们一定会环中相遇，否则fast会指向链表的最后一个节点或最后一个节点的next。
代码实现：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head == NULL || head->next == NULL){return NULL;}ListNode* slow = head;ListNode* fast = head;///找到环中的相遇节点xwhile(true){if(fast == NULL || fast->next == NULL){return NULL;}slow = slow->next;fast = fast->next->next;if(slow == fast){break;}}if(fast == slow){return fast;}else{return NULL;}}
};

(9) 找到环形链表中环的入口
基本思想： 同样是使用快慢指针，如果链表中有环，先找两个指针在环中的相遇节点，然后令fast指向相遇节点x，slow指向头节点，两个指针每次走一步，则它们最终会在环的入口处相遇；
理由如下：
如下图所示：

假设相遇时slow走的路程$s=a+x$，$a$为链表头到环入口的距离，$x$为环入口到相遇点的距离；

因为fast每次比slow多走两步,故fast走的路程为$2s=nc+s$，$c$为环的长度;

根据以上两式有 $s=nc=a+x$，再经过变换，得到$a=nc-x=(n-1)c+(c-x)$，而$c-x$刚好为相遇点到环入口的长度，所以

如果一个指针从链表的头节点开始走，另一个从相遇点开始走，两个指针每次走相同的步长，则它们一定会在环入口相遇。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head == NULL || head->next == NULL){return NULL;}ListNode* slow = head;ListNode* fast = head;///找到环中的相遇节点xwhile(true){if(fast == NULL || fast->next == NULL){return NULL;}slow = slow->next;fast = fast->next->next;if(slow == fast){break;}}//如果链表中有环，令fast指向相遇节点x,slow指向头节点，两个指针每次走一步，//则它们最终会在环的入口处相遇；//理由如下：//假设相遇时slow走的路程s=a+x,a为链表头到环入口的距离，x为环入口到相遇点的距离；//因为fast每次比slow多走两步,故fast走的路程为2s= nc+s,c为环的长度;//根据以上两式有 s=nc=a+x,所以a=nc-x=(n-1)c+(c-x),而c-x刚好为相遇点到环入口的长度,所以//如果一个指针从链表的头节点开始走，另一个从相遇点开始走，两个指针每次走相同的步长，则一定会在环入口相遇。if(fast == slow){slow = head;while(slow != fast){slow = slow->next;fast = fast->next;}return fast;}else{return NULL;}}
};

(10) 求环形链表中环的长度
**基本思想：**同样使用快慢指针，找到环中的两指针的相遇节点，然后从该节点开始计数，看经过多少个节点回到该节点的本身，经过的节点数量即为环的长度
代码实现：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head == NULL || head->next == NULL){return NULL;}ListNode* slow = head;ListNode* fast = head;///找到环中的相遇节点xwhile(true){if(fast == NULL || fast->next == NULL){return NULL;}slow = slow->next;fast = fast->next->next;if(slow == fast){break;}}if(fast == slow){ListNode* dump = fast;int count = 0;while(true){fast = fast->next;cout++;if(fast == dump){break;}}return fast;}else{return NULL;}}
};