单链表算法题(二）（超详细版）
前言 : 通过算法题 ， 学习解决问题的思路 ， 再面对类似的算法题时 ， 能快速定位解决方案
一 . 链表的回文结构
链表的回文结构 : 链表的回文结构_牛客题霸_牛客网
思路一 :
创建新链表 ， 对原链表进行反转，结果存储在新链表中，然后遍历新旧链表进行比较
思路二 ：
因为牛客网里给了 ---> 链表的长度小于等于900 的这个条件 ， 所以我们可以创建一个新数组，遍历链表，把链表里的值存储在数组中，然后定义两个变量(left,right)，分别指向数组的最左端和最右段，然后进行对比，相等的时候，left++,right--
1 . 创建数组
2 . 遍历链表，把 链表结点的值 存到数组中
3 . 创建两个变量 （left = 0 , right = i-1)
4 . left 与 right 往中间走 ，相等继续往中间走，都相等返回true , 不相等时返回false
思路三 ：
1 . 找到中间结点（快慢指针）
2 . 反转以中间结点为头的链表（三指针法）
3 . 遍历【原链表】和【以中间结点为头】的链表
思路二代码：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
// write code here
int arr[900] = {0};
int i = 0;
ListNode* pcur = A;
//遍历链表，赋值给数组
while(pcur){
arr[i++] = pcur->val;
pcur = pcur->next;
}
int left = 0;
int right = i-1;
while(left < right)
{
if(arr[left] != arr[right])
{
return false;
}
left++;
right--;
}
return true;;
}
};思路三代码 : 快慢指针和三指针法在单链表算法题(一）（超详细版）-CSDN博客有详细说明
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* reverseList( ListNode* head) {
if(head == NULL)
{
return head;
}
ListNode* n1,*n2,*n3;
n1 = NULL;
n2 = head;
n3 = head->next;
while(n2)
{
n2->next = n1 ;
n1 = n2 ;
n2 = n3 ;
if(n3)
n3 = n2->next;
}
return n1;
}
bool chkPalindrome(ListNode* A) {
//1.找到中间结点
ListNode* mid = middleNode(A);
//2.反转以中间结点为头的链表
ListNode* right = reverseList(mid);
//3. 遍历左右链表
ListNode* left = A;
while(right)
{
if(left->val != right->val)
{
return false;;
}
left = left->next;
right = right->next;
}
return true;
}
};二 . 相交链表
相交链表 : . - 力扣（LeetCode）
思路 :
1 . 求两个链表的长度
2 . 计算两个链表的长度差
3 . 找到大/小链表，让大链表先走 长度差步
4 . 遍历两个链表，比较是否存在相同的结点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
//计算两个链表长度
ListNode* pa = headA , *pb = headB;
int sizeA = 0,sizeB = 0;
while(pa){
++sizeA;
pa = pa->next;
}
while(pb)
{
++sizeB;
pb = pb->next;
}
//计算长度差 -- 绝对值(可以使用函数abs)
int gap = abs(sizeA - sizeB);
//找大小链表 -- 让大链表走gap 步
ListNode* longList = headA;
ListNode* shortList = headB;
if(sizeA < sizeB){
longList = headB;
shortList = headA;
}
while(gap--)
{
longList = longList->next;
}
//遍历链表 -- 找相交结点
//存在相交结点
while(longList){
if(longList == shortList){
return longList;
}
longList = longList->next;
shortList = shortList->next;
}
//不存在相交结点
return NULL;
}三 . 环形链表I
环形链表I : . - 力扣（LeetCode）
思路 : 快慢指针
慢指针每次走一步，快指针每次走两步 ，两个指针从链表起始的位置开始运行；若链表带环 ，快指针在环内追逐 ，快慢指针会相遇 ； 若不带环 ，快指针率先走到链表的末尾 ；
这道题重在证明思路 :
1 ) 为什么慢指针每次走一步，快指针每次走两步，快慢指针会相遇？会遇不上吗？
2 ) 快指针能不能一次走3步，走4步，...n步？
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
//快慢指针相遇，存在环
if(slow == fast)
{
return true;
}
}
//没相遇，不存在环
return false;
}3.1 证明一：
1 ) 为什么慢指针每次走一步，快指针每次走两步，快慢指针会相遇？会遇不上吗？
fast 一次走两步 ， slow 一次走一步 ， 如果链表中存在环 ， 那么快指针先进入环 ，假设slow也走完入环前的距离为N（最大距离），在接下来的追逐过程中，每追击一次，他们之间的距离缩小一步
追击过程中 fast 和slow 的变化 :
N - 1 => N - 2 => N-3 => ...... => 2 => 1 => 0 (相遇了）
3.2 证明二 ：
2 ) 快指针能不能一次走3步，走4步，...n步？
按照上面的分析，慢指针每次走一步，快指针每次走三步，此时快慢指针的最大距离为N，接下来的追逐中，每追逐一次，他们之间的距离缩小2步
追逐过程中fast和slow之间的距离变化：
分析 :
1 . 如果N是偶数 ， 第一轮就追上了
2 . 如果N是奇数 ， 第一轮追不上，错过了，距离变为-1，即C-1 ， 进入新的一轮追击
1） C-1如果是偶数，那么下一轮就追上了
2） C-1如果是奇数，那么就追不上
总结一下追不上的条件 :N是奇数，C是偶数 (证明是否存在N为奇数，C为偶数的情形）
假设 :
环的周长为C，头结点到slow的长度为L ， slow 走一步 ，falst 走三步 ， 当slow 指针 入环后，slow和fast 指针在环中开始进行追逐 ， 假设此时的fast 已经绕环 n 周
同理 : 对快指针走 4 ， 5 ... 步最终也会相遇，证明方法同上！
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode* head) {
ListNode *slow, *fast;
slow = fast = head;
while (fast && fast->next) {
slow = slow->next;
int n = 3; // fast每次⾛三步
while (n--) {
if (fast->next)
fast = fast->next;
else
return false;
}
if (slow == fast) {
return true;
}
}
return false;
}提示 ：
虽然已经证明了 ， 快指针无论走多少步都可以满足在带环链表中相遇 ， 但是在编写代码的时候，会有额外的步骤引入，涉及快慢指针的算法题中，通常习惯使用快指针每次走两步，慢指针走一步的方式。
四 . 环形链表II
环形链表II :. - 力扣（LeetCode）
主要思路 : 快慢指针的思想
(快指针 fast 每次走两步 , 慢指针 slow 每次走一步)
创建两个指针(快慢指针) , 如果链表带环 , 存在相遇结点 , 此时的相遇结点到入环结点的距离与头结点到入环结点的距离 相同 !
1 . 创建指针变量(快慢指针)
2 . 判断快慢指针走到的结点是否相同 ---> 相同(带环)
3 . 创建指针变量(pcur)(初始化为头结点)
4 . pcur 与 slow 不相等时 , 两个指针一直往后走
5 . 返回相等时的结点
证明 : 为什么带环链表中 , 相遇点到入环结点的距离 等于 头结点到入环结点的距离?
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
ListNode* fast = head,*slow = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
//相遇点
if(slow == fast)
{
ListNode* pcur = head;
while(slow != pcur)
{
pcur = pcur->next;
slow = slow->next;
}
//找到入环点了
return pcur;
}
}
return NULL;
}4.1 证明
证明 : 为什么带环链表中 , 相遇点到入环结点的距离 等于 头结点到入环结点的距离?
( 如下图 )
假设 : 头结点到入环结点的距离为 L , 相遇结点为M , 环的长度为X , 链表如果带环 , 在相遇点 , 快指针到入环结点的距离为 R-L
1 . 求出相遇时 , 快慢指针所走的路径长度
fast = L + X + nR
slow = L + X
注 : 当慢指针进入环的时候 , 快指针可能已经在环中绕了n 圈 , n 至少为 1 (因为快指针先进环 ,先走到 M的位置 , 最后在M的位置和慢指针相遇)
2 . 快指针 = 2 * 慢指针
fast = 2 * slow
L + X + nR = 2 * ( L + X )
nR = L + X
( n-1 )R + R - X = L
( n 为 1, 2 , 3 , 4 .... , n 的大小取决于环的大小 , 环越小n 越大)
极端情况下 , 假设 n = 1 , 此时 : L = R - X
即 : 一个指针从链表起始结点运行 , 一个指针从相遇结点绕环 , 每次走一步 , 两个指针最终会在入口结点相遇
五 . 随机链表的复制
随机链表的复制 : . - 力扣（LeetCode）
难点 ： 深拷贝 --> 重新申请一块空间存储一样的结点 ---> 可是如果创建新链表 ， 但是random 指向的结点还没有创建好 ， 会报错，非法访问空间
所以我们可以在原链表中 , 先把值进行拷贝 , 然后此时random 指向的结点是存在的 ,通过遍历拷贝的结点 和 原链表的结点把random的指向处理好 , 最后断开与原链表的结点的连接即可
1 ) 拷贝结点
2 ) 置random
3 ) 断开连接
注意 : 当链表为空时 ,直接返回head
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *next;
* struct Node *random;
* };
*/
typedef struct Node Node;
Node* buyNode(int x)
{
Node* node = (Node*)malloc(sizeof(Node));
node->val = x ;
node->next = node->random = NULL;
return node;
}
void AddNode(Node* head)
{
Node* pcur = head;
while(pcur)
{
Node* next = pcur->next;
Node* newnode = buyNode(pcur->val);
//尾插
newnode->next = next;
pcur->next = newnode;
pcur = next;
}
}
void SetRandom(Node* head)
{
Node* pcur = head;
while(pcur)
{
Node* copy = pcur->next;
if(pcur->random)
copy->random = pcur->random->next;
pcur = copy->next;
}
}
struct Node* copyRandomList(struct Node* head) {
if(head == NULL)
{
return head;
}
//1.拷贝结点
AddNode(head);
//2.置randow
SetRandom(head);
//3.断开链表
Node* pcur = head;
Node* newHead,*newTail;
newHead = newTail = pcur->next;
while(newTail->next)
{
pcur = newTail->next;
newTail->next = pcur->next;
newTail = pcur->next;
}
return newHead;
}
写算法题目时 , 如果暂时没有解题思路可以先画画图 , 打开新大陆!
原文地址：https://blog.csdn.net/khjjjgd/article/details/142963909
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！