小小林熬夜学编程

这个屌丝很懒，什么也没留下！

热门标签

1. 链表_链表访问

作者：小小林熬夜学编程 | 2024-05-07 11:42:51

踩

链表访问

一、什么是链表？

线性表是很常用的数据结构，分为顺序表和链表。
按照正常方式定义以一个数组，计算机会从内存中取出一块连续的地址来存放给定长度的数组；而链表则由若干个节点组成，且结点在内存中的存储位置不连续，链表的两个节点之间一半由一个指针从一个结点指向另一个结点，故链表结点由两部分组成：即数据域和指针域。

程序内部
在这里插入图片描述

链表中的每个节点至少包含数据域和指针域
链表中的每个节点，通过指针域的值，形成一个线性结构
查找节点 O(n)，插入节点 O(1)，删除节点 O(1)
不适合快速的定位数据，适合动态插入和删除的场景

单向链表与数组
单向链表：必须挨个查找元素 ——>>查找节点 O(n)，插入节点 O(1)，删除节点 O(1)
数组：可以随机访问元素——>>查找节点 O(1)，插入节点 O(n)，删除节点 O(n)

二、经典的链表实现方法

struct Node {
	Node(int data):data(data),next(NULL){} //node构造函数
	int data;
	int *next;
};

1
2
3
4
5
6

int data[10];
int next[10];

//ind 后添加节点 p ，节点p中值为val
void add(int ind, int p, int val) {
	next[ind] = p;
	data[p] = val;
	return ;
}
1
2
3
4
5
6
7
8
9

三、应用场景

1.操作系统内的动态内存分配

原有4G , malloc（1GB),分块后以链表链接
在这里插入图片描述

2.LRU缓存淘汰算法

插入数据5，插入到尾部，删除数据1
在这里插入图片描述

四、经典面试题

1. 链表的访问

环形链表
在这里插入图片描述
a.如何判定链表有环
方法1：遍历整个链表，创建一个哈希表来存储遍历过的节点(需要开辟新内存)

方法2：快慢指针
快指针每次走两步，慢指针每次走一步，如果链表有环，则快慢指针一定会相遇，当指向同一个节点时，遍历结束

LeetCode 141. 环形链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == nullptr) return false;
        ListNode *p = head,*q = head->next;
        while(p != q && q && q->next){
            p = p->next;
            q = q->next->next;
        }
        return q && q->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

b.如何判定环的起始位置
将一个指针放在链表起始位置，另一个指针放在相遇位置，两个指针一起朝后走，相遇位置就是环的起始位置

LeetCode 142.环形链表Ⅱ

//8ms
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == nullptr) return nullptr;
        ListNode *p = head, *q = head->next;
        while(p != q && q && q->next){
            p = p->next;
            q = q->next->next;
        }
        if(q == nullptr || q->next == nullptr) return nullptr;
        p = head->next;
        q = head->next->next;
        while(p != q){
            p = p->next;
            q = q->next->next;
        }
        p = head;
        while(p != q){
            p = p->next;
            q = q->next;
        }
        return q;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

//4ms
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == nullptr) return nullptr;
        ListNode *p = head, *q = head;
        if(q->next == nullptr) return nullptr;
        do{
            p = p->next;
            q = q->next->next;
        }while(p != q && q && q->next);
        if(q == nullptr || q->next ==nullptr) return nullptr;
        p = head;
        while(p != q) p = p->next,q = q->next;
        return q;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

LeetCode 202.快乐数

[快乐数] 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false

在这里插入图片描述
题目转化为：判断链表是否有环
如果遍历某个节点为1，说明无环，是快乐数
如果遍历到重复的节点值，说明有环，不是快乐数

class Solution {
public:
    int getNext(int x){
        int z = 0;
        while(x){
            z += (x % 10) * (x % 10);
            x /= 10;
        }
        return z;
    }



    bool isHappy(int n) {
            int p = n, q = n;
            do{
                p = getNext(p);
                q = getNext(getNext(q));
            }while(p != q  && q != 1);
            return q == 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2. 链表反转

cur——> null
pre移动到cur所在位置，移动cur到next所在位置，next也后移（ pre 指向反转头，cur指向未反转头）

在这里插入图片描述

3.重复上述操作

LeetCode 206.反转链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr) return head;
        ListNode *pre = nullptr, *cur = head, *p = head->next;
        while(cur){//未翻转部分不为空时
            cur->next = pre;
            pre = cur;
            (cur = p) && (p = p->next);
        }
        return pre;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

递归实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode *tail = head->next,*p = reverseList(head->next);//记录下一个节点地址
        head->next = tail->next;
        tail->next = head;
        return p;
    }
};
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

翻转前n个节点

Node *reverse(Node *head,int n){
	if(n == 1) return head;
	Node *tail = head->next, *p = reverse(head->next,n-1);
	head->next = tail->next;
	tail->next = head;
	return p;
}
1
2
3
4
5
6
7

LeetCode 92.翻转从m到n的链表

采用虚拟头节点
找到要反转的第一个节点，以此为新链表翻转前m-n+1位，再将第一个节点指向头节点。

class Solution {
public:
    ListNode *reverseN(ListNode *head,int n){
        if(n == 1) return head;
        ListNode *tail = head->next, *p = reverseN(head->next, n-1);
        head->next = tail->next;
        tail->next = head;
        return p;
    } 

    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode ret(0,head),*p = &ret;
        int cnt = right - left + 1;
        while(--left) p = p->next;
        p->next = reverseN(p->next, cnt);
        return ret.next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

LeetCode 25.K个一组翻转链表

1.加虚拟头，p->虚拟头，q = p->next

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* __reverseN(ListNode* head, int n){
        if(n == 1) return head;
        ListNode *tail = head->next, *p = __reverseN(head->next, n-1);
        head->next = tail->next;
        tail->next = head;
        return p;
    }
    ListNode* reverseN(ListNode* head, int n){
        ListNode *p = head;
        int cnt = n;
        while(--n && p) p = p->next;
        if(p == nullptr) return head;
        return __reverseN(head,cnt);
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode ret(0,head), *p = &ret, *q = p->next;
        while((p->next = reverseN(q, k)) != q){
            p = q;
            q = p->next;
        }
        return ret.next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

LeetCode 61.旋转链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head == nullptr) return nullptr;
        int n = 1;
        ListNode *p = head;
        while(p->next)  p = p->next, n += 1;
        p->next = head;
        k %= n;
        k = n - k;
        while(k--) p = p->next;
        head = p->next;
        p->next = nullptr;
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

3. 链表删除操作

LeetCode 19.删除链表的倒数第N个结点

设置两个指针，q先走N步，然后p,q一起走直到q指向null时，p指向删除节点的前一个结点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
                    ListNode ret(0,head), *p = &ret, *q = head;
            while(n--){
                q = q->next;
            }
            while(q){
                p = p->next;
                q = q->next;
            }
            p->next = p->next->next;
            return ret.next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

LeetCode 83. 删除排序链表中的重复元素

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == nullptr) return nullptr;
        ListNode *p = head;
        while(p->next){
            if(p->val == p->next->val){
                p->next = p->next->next;
            }else{
                p = p->next;
            }
        }
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

LeetCode 82. 删除排序链表中的重复元素 II

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == nullptr) return nullptr;
        ListNode ret(0,head), *p = &ret, *q;
        while(p->next){
            if(p->next->next && p->next->val == p->next->next->val){
                q = p->next->next;
                while(q && q->val == p->next->val) q = q->next;
                p->next = q;
            }else{
                p = p->next;
            }
        }
        return ret.next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

4.什么时候使用虚拟头指针？

链表的头地址可能发生改变时使用虚拟头指针

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/549038