当前位置：首页 > news >正文

【数据结构】链表经典OJ题，常见几类题型（一）

news 来源：原创 2024/5/20 13:03:28

题型一：反转单链表

思路解析

反转一个链表主要是想让第一个节点指向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;}
};