【数据结构】链表经典OJ题，常见几类题型（一）
【数据结构】链表经典OJ题，常见几类题型（一）
题型一：反转单链表
思路解析
反转一个链表主要是想让第一个节点指向
NULL，第二个节点指向第一个，以此类推。那么我们不难想到，想要反转其中一个节点，两个指针肯定是不够的，所以这就要求我们定义三个指针：分别指向当前节点n2，前一个节点n1，后一个节点n3。 这里定义的三个指针主要作用：n1是为了能让当前节点能指向前一个节点地址，而n1就是记录前一个节点的地址，n3是为了在反转当前节点后，能找到后一个节点的地址。 那么定义一个循环后依此思路便可反转链表了。当然循环结束的条件为n3 == NULL，那么再仔细想一下，其实还有最后一个节点没有反转，此节点只需要最后单独反转便可。那么为什么不让循环结束条件为n2 == NULL呢？是因为此时n3 == n2->next而n2又等于NULL，这就导致了错误。 还要一点需要注意的是：在解题前我们还要单独判断一下此链表是否为空。
图解如下：
OJ题实例
LeetCode链接：206. 反转链表
解题代码
struct ListNode* reverseList(struct ListNode* head)
{
//判断链表为空的情况
if(head==NULL)
{
return NULL;
}
else
{
//反转链表
struct ListNode* n1=NULL;
struct ListNode* n2=head;
struct ListNode* n3=head->next;
while(n3)
{
n2->next=n1;
n1=n2;
n2=n3;
n3=n3->next;
}
//最后一个节点的判断
n2->next=n1;
return n2;
}
}题型二：快慢指针
思路解析
通常快慢指针方法出现在需要找链表中间节点，链表带环等题型中。快慢指针的逻辑思路如下： 先定义两个结构体指针
struct ListNode* slow = head, *fast = head;，先将他们指向头节点，在写一个循环，每次循环慢指针向后走一个节点，即slow = slow->next;，快指针向后走两个节点，即fast = fast->next->next;，循环的判断条件为fast != NULL && fast->next != NULL，这样便很好解决了链表为空和只有一个节点的情况。需要注意的是如果节点数为奇slow刚好在中间节点，节点数为偶slow在中间两个节点的后一个。
OJ题实例
LeetCode链接: 876. 链表的中间结点
解题代码
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast=head, *slow=head;
while(fast && fast->next)
{
slow = slow -> next;
fast = fast -> next -> next;
}
return slow;
}两类题型的结合
牛客链接: OR36 链表的回文结构
解题思路： 此题可以先找到中间节点，然后把后半部分逆置，然后进行前后两部分一一比对，如果节点的值全部相同，则即为回文。
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
if (A == NULL || A->next == NULL)
return true;
ListNode* slow, *fast, *prev, *cur, *nxt;
slow = fast = A;
//找到中间节点，即题型二快慢指针
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
prev = NULL;
//后半部分逆置，即题型一链反转
cur = slow;
while (cur)
{
nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
//逐点比对
while (A && prev)
{
if (A->val != prev->val)
return false;
A = A->next;
prev = prev->next;
}
return true;
}
};