五个经典链表OJ题带你进阶C++链表篇
1. 题目：反转链表
题目描述：
输入一个链表，反转链表后，输出新链表的表头。
示例输入：
1 -> 2 -> 3 -> 4 -> 5
示例输出：
5 -> 4 -> 3 -> 2 -> 1
思路分析：
1、定义三个指针：当前节点指针pNode、当前节点的前一个节点指针pPrev、当前节点的后一个节点指针pNext。
2、遍历链表，将当前节点的指针修改为空时，循环停止；每次将pNode的next指针指向pPrev节点，再将三个指针向后移动。
3、最后返回pPrev节点，也就是反转后的新链表表头。
代码实现：
struct ListNode* ReverseList(struct ListNode* pHead) {
if(pHead == NULL || pHead->next == NULL)
return pHead;
struct ListNode* pNode = pHead;
struct ListNode* pPrev = NULL;
while(pNode != NULL) {
struct ListNode* pNext = pNode->next;
pNode->next = pPrev;
pPrev = pNode;
pNode = pNext;
}
return pPrev;
}
2. 题目：合并两个有序链表
题目描述：
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
示例输入：
1 -> 2 -> 4, 3 -> 5 -> 6
示例输出：
1 -> 2 -> 3 -> 4 -> 5 -> 6
思路分析：
1、将两个链表从头开始比较，较小的元素节点先链接到新的链表中。
2、递归执行比较和链接操作，直到其中一个链表为空。
3、将另一个非空的链表链接到新的链表的末尾。
4、最后返回新建链表的头结点。
代码实现：
struct ListNode* MergeList(struct ListNode* p1, struct ListNode* p2) {
if(p1 == NULL)
return p2;
if(p2 == NULL)
return p1;
struct ListNode* pNew = NULL;
if(p1->val < p2->val) {
pNew = p1;
pNew->next = MergeList(p1->next, p2);
} else {
pNew = p2;
pNew->next = MergeList(p1, p2->next);
}
return pNew;
}
3. 题目：找到链表的倒数第 k 个节点
题目描述：
输入一个链表，输出该链表中倒数第k个结点。
示例输入：
1 -> 2 -> 3 -> 4 -> 5, 2
示例输出：
4 -> 5
思路分析：
1、分别定义两个指针：pAhead 和 pBehind。
2、首先让 pAhead 节点移动 K 个节点，然后 pAhead 节点和 pBehind 节点同时向后移动，直到pAhead节点到链表末端。
3、此时的 pBehind 就是倒数第 K 个节点。
代码实现：
struct ListNode* FindKthToTail(struct ListNode* pListHead, unsigned int k) {
if(pListHead == NULL)
return NULL;
struct ListNode* pBehind = pListHead;
struct ListNode* pAhead = pListHead;
for(int i = 0; i < k - 1; i++){
if(pAhead->next != NULL)
pAhead = pAhead->next;
else
return NULL;
}
while(pAhead->next != NULL) {
pAhead = pAhead->next;
pBehind = pBehind->next;
}
return pBehind;
}
4. 题目：删除链表中重复的结点
题目描述：
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
示例输入：
1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
示例输出：
1 -> 2 -> 5
思路分析：
1、使用一个指针pNode遍历链表，判断当前节点是否与下一个节点重复。
2、如果重复，则删除当前节点和下一个节点，同时将前一个节点的next指向下一个节点。
3、如果不重复，则继续向后遍历。
4、最后返回修改后的链表头指针。
代码实现：
struct ListNode* deleteDuplication(struct ListNode* pHead) {
if(pHead == NULL)
return NULL;
struct ListNode* pNode = pHead;
struct ListNode* pPrev = NULL;
while(pNode != NULL) {
struct ListNode* pNext = pNode->next;
if(pNext != NULL && pNode->val == pNext->val) {
while(pNext != NULL && pNode->val == pNext->val)
pNext = pNext->next;
if(pPrev == NULL)
pHead = pNext;
else
pPrev->next = pNext;
} else {
pPrev = pNode;
}
pNode = pNext;
}
return pHead;
}
5. 题目：判断链表中是否有环
题目描述：
给定一个链表，判断链表中是否有环。
示例输入：
1 -> 2 -> 3 -> 4 -> 5 -> 3
示例输出：
true
思路分析：
1、使用快慢指针，如果在遍历中两个指针相遇了，说明链表中存在环。
2、如果快指针pFast遍历过程中到达了链表末端，仍未与慢指针pSlow相遇，则链表中不存在环。
代码实现：
bool hasCycle(struct ListNode *head) {
if(head == NULL)
return false;
struct ListNode *pSlow = head, *pFast = head->next;
while(pFast != NULL && pFast->next != NULL) {
if(pFast == pSlow)
return true;
pSlow = pSlow->next;
pFast = pFast->next->next;
}
return false;
}