线性结构

链表

删除节点 o(1)

将下一节点数据复制到此节点，删除下一节点

单链表转置

//单链表的转置,循环方法
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;
}
//单链表的转置,递归方法
Node* reverseByRecursion(Node *head)
{
	//第一个条件是判断异常，第二个条件是结束判断
	if(head == NULL || head->next == NULL) 
		return head;
	Node *newHead = reverseByRecursion(head->next);
	head->next->next = head;
	head->next = NULL;
	return newHead;    //返回新链表的头指针
}

检测链表是否有环

	两个指针片fast、slow对链表进行遍历，每次循环中slow走一步，fast走两步，如果链表有环，fast会在领先slow一圈后与slow指在同一位置。

bool IsExitsLoop(slist *head)
{
	slist *slow = head, *fast = head;

	while ( fast && fast->next ) 
	{
		slow = slow->next;
		fast = fast->next->next;
		if ( slow == fast ) break;
	}

	return !(fast == NULL || fast->next == NULL);
}

找到环入口点

fast速度是slow两倍，且fast先进入环，所以相遇时，fast已经绕环n圈，而slow一圈还未绕完。假设slow走过s个节点，则fast走过2s个节点，设环长为r个节点 2s=s+nr s=nr 设链表长为L个节点，起点距环入口点长为a个节点，环入口点距相遇点为x个节点 a+x=nr=(n-1)r+L-a a=(n-1)r+(L-a-x) L-a-x即为相遇点到环入口点的距离 所以用两个指针分别从起点和相遇点出发，每次一步，两个指针相等时是环入口点

slist* FindLoopPort(slist *head)
{
	slist *slow = head, *fast = head;

	while ( fast && fast->next ) 
	{
		slow = slow->next;
		fast = fast->next->next;
		if ( slow == fast ) break;
	}

	if (fast == NULL || fast->next == NULL)
		return NULL;

	slow = head;
	while (slow != fast)
	{
			slow = slow->next;
			fast = fast->next;
	}

	return slow;
}

检测两个链表是否交叉（不存在环）

	两个链表尾部一样即交叉
	遍历两个链表，长链表先走两链表长度之差步，之后每次一步，两节点相等即为交叉位置

栈

自增操作符实现原理

以y=i++；为例 1.i值进栈 2.复制一份i值进栈 3.1进栈 4.1和i出栈进行加操作，结果s入栈 5.s出栈，赋给i 6.i出栈，赋给y 所以语句i=i++;执行后i值不变。 以y=++i; 为例 1.i值进栈 2.1入栈 3.1和i出栈，进行加操作，结果s入栈 4.栈顶的s复制一份s'入栈 5.将s'弹出，赋给i 6.将s弹出，赋给y

1. 找出链表倒数第k个数 使用双指针，间隔k位，向后移动。前指针走到最后一位时，后指针是倒数第k位。

2. 检测是否是回文链表 将前半部分压栈，然后每次弹出栈顶与剩余部分比较。 所以关键是如何找到链表中部：使用快慢指针，快指针每次走两步，慢指针走一步，当快指针走到尾部时，慢指针走了一半。