算法与数据结构基础系列（一）：链表的常见问题分析及实现

本文对链表的常见问题进行总结和归纳：

定义链表的数据结构如下：

struct ListNode{
        int value;
        ListNode *next;
}

问题一：求单链表中节点的个数

unsigned int GetListLength(ListNode *pHead) {
	if (pHead == NULL) { //判断是否为空链表
		return 0;
	}

	unsigned int ListLength = 0;
	ListNode * pCurrent = pHead;
	while (pCurrent) {
		ListLength++;
		pCurrent = pCurrent->next;
	}
	return ListLength;
}

问题二：单链表的原地翻转

ListNode * RevertList(ListNode * pHead) {
	if (pHead == NULL || pHead->next == NULL) {
		return pHead;
	}
	ListNode * pRevertListHead = NULL;
	ListNode * pCurrent = pHead;

	while (pCurrent){
		ListNode * pTemp = pCurrent;
		pCurrent = pCurrent->next;
		pTemp->next = pRevertListHead;
		pRevertListHead = pTemp;
	}
	return pRevertListHead;
}

问题三：求链表的倒数第K个节点

ListNode * GetKthNode(ListNode * pHead, unsigned int k) {

	if (pHead == NULL || k == 0) {
		return NULL;
	}

	ListNode * pAhead = pHead;
	ListNode * pBehand = pHead;

	for (int i = 1; i < k; i++) {
		if (pAhead->next) {
			pAhead = pAhead->next;
		}
		else { // 节点数小于k
			return NULL;
		}
	}

	while (pAhead->next != NULL) { // 两个指针同时移动，当第一个指针指向链表尾部的时候，第二个指针刚好走到倒数第k个节点
		pAhead = pAhead->next;
		pBehand = pBehand->next;
	}

	return pBehand;
}

问题四：求一个链表的中间节点

ListNode * FindMidNode(ListNode * pHead) {

	if (pHead == NULL || pHead->next == NULL) { // 空链表或者链表节点数为1，返回NULL
		return NULL;
	}

	// 初始化
	ListNode * pAhead = pHead;
	ListNode * pBehind = pHead;

	// 一个指针每次前进两步，一个指针每次前进一步，当走两步的指针走到终点时，走一步的指针指向为中间节点
	while (pAhead->next) {
		pAhead = pAhead->next;
		pBehind = pBehind->next;
		if (pAhead->next) {
			pAhead = pAhead->next;
		}
	}
	return pBehind;

}

问题五：合并两个有序的链表

// 合并两个有序的链表
ListNode * MergeTwoSortedListNode(ListNode * pHead1, ListNode * pHead2) {

	// 特殊情况处理
	if (pHead1 == NULL) {
		return pHead2;
	}
	if (pHead2 == NULL) {
		return pHead1;
	}

	// 合并后的头指针
	ListNode * pMerged = NULL;

	if (pHead1->value <= pHead2->value) {
		pMerged = pHead1;
		pHead1 = pHead1->next;
	}else {
		pMerged = pHead2;
		pHead2 = pHead2->next;
	}

	pMerged->next = NULL;

	ListNode * pTemp = pMerged; // pTemp用于指向最新合并的节点
	while (pHead1 != NULL && pHead2 != NULL) {
		if (pHead1->value <= pHead2->value) {
			pTemp->next = pHead1;
			pHead1 = pHead1->next;
			pTemp = pTemp->next;
		}else {
			pTemp->next = pHead2;
			pHead2 = pHead2->next;
			pTemp = pTemp->next;
		}
		pTemp->next = NULL;
	}
	
	// 循环结束后将 pTemp 值设置为当前指针不为空的链表指针
	if (pHead1) {
		pTemp = pHead1;
	}
	else if(pHead2) {
		pTemp = pHead2;
	}

	return pMerged;
}

问题六：判断一个链表是否有环

// 判断一个链表是否有环
bool IsCircle(ListNode *pHead) {
	ListNode * pFast = pHead;
	ListNode * pSlow = pHead;
	while (pFast->next != NULL && pFast != NULL) {
		pFast = pFast->next->next;
		pSlow = pSlow->next;
		if (pFast == pSlow) {
			return true;
		}
	}
	return false;
}

问题七：判断两个链表是否相交

// 判断两个链表是否相交
bool IsCrossing(ListNode * pFistHead, ListNode * pSecondHead) {
	if (pFistHead == NULL || pSecondHead == NULL) {
		return false;
	}
	
	ListNode *ptemp1 = pFistHead;
	ListNode *ptemp2 = pSecondHead;
	
	while (ptemp1 != NULL) {
		ptemp1 = ptemp1->next;
	}

	while (ptemp2 != NULL) {
		ptemp2 = ptemp2->next;
	}
	return ptemp1 == ptemp2;
}

问题八：求两个相交链表相交的第一个节点

// 找出两个相交链表的第一个相同的节点
ListNode * FindTheFirstCommonNode(ListNode * pHead1, ListNode * pHead2) {
	if (pHead1 == NULL || pHead2 == NULL) { // 其中一个链表为空
		return NULL;
	}
	
	int length1 = 1;
	int length2 = 1;
	int length;
	ListNode * pTemp1 = pHead1;
	ListNode * pTemp2 = pHead2;

	while (pTemp1 != NULL) {
		pTemp1 = pTemp1->next;
		length1++;
	}

	while (pTemp2 != NULL) {
		pTemp2 = pTemp2->next;
		length2++;
	}

	if (pTemp1 != pTemp2) { // 两个链表不相交
		return NULL;
	}

	pTemp1 = pHead1;
	pTemp2 = pHead2;

	if (length1 > length2) {
		length = length1 - length2;
		while (length > 0) {
			pTemp1 = pTemp1->next;
			length--;
		}
	}
	else {
		length = length2 - length1;
		while (length > 0) {
			pTemp2 = pTemp2->next;
			length--;
		}
	}

	while (pTemp1 != pTemp2) {
		pTemp1 = pTemp1->next;
		pTemp2 = pTemp2->next;
	}

	return pTemp1;

}

问题九：求一个带环链表的环的入口

如上图所示，当环的长度(b+c)，大于进入环之前的长度(a)时，我们可以用一快一慢两个指针分别从头开始前进，快指针一次前进两步，慢的指针一次前进一步。当两个指针第一次相遇时z点，快指针走过的距离刚好是慢指针的两倍，那么快指针走过的长度为 a+b+c+b,慢指针走过的长度为 a+b,根据 a+b+c+b = 2（a+b），显然就有 a = c，即在相遇的地点，让慢指针从头开始走，快指针每次前进一步，再次相遇的地点即为环的入口。当然，当环的长度小于进入环之前的长度，其实也是满足的，不同之处在于，相遇前快指针会绕环 n 周，这个可以从数学上去证明，下面给出代码实现：
```
// 求有环链表的第一个节点
ListNode * FirstListNode(ListNode * pHead) {
	if (pHead == NULL || pHead->next == NULL) {
		return NULL;
	}
	
	ListNode * pFast = pHead;
	ListNode * pSlow = pHead;
	
	while (pFast != NULL && pFast->next != NULL) {
		pFast = pFast->next->next;
		pSlow = pSlow->next;
		if (pFast == pSlow) { // 有环
			pSlow = pHead;
			while (pSlow != pFast) {
				pFast = pFast->next;
				pSlow = pSlow->next;
			}
			return pFast;
		}
	}
	return NULL;
}
```
问题十：

算法与数据结构基础系列（一）： 链表的常见问题分析及实现

算法与数据结构基础系列（一）：链表的常见问题分析及实现