单链表 – enoine

链表理论基础:

链表是一种通过指针串联在一起的线性结构,每一个节点都由两部分组成,一个是数据域,另一个是指针域(存放指向下一个节点的指针),最后一个的节点的指针域指向NULL(空指针)

链接的入口点称为链表的头节点,也就是head.

单链表的构造结构:

链表的存储方式:

数组在内存中是连续分布的,但链表在内存中不是连续分布的.链表是通过指针域的指针来链结内存中各个节点的,所以链表中的节点在内存中不是连续分布的,而是散乱分布在内存中的某地址上,分配机制取决于操作系统的内存管理

定义:

struct ListNode{
    int val;//节点的值
    ListNode *next;//指向下一个节点的指针
    ListNode(int x):val(x),next(nullptr){}//构造函数
};

1.删除节点

删除D节点:

只要将C节点的next指针指向E节点就可以了.

疑问:节点D不是依然存留在内存中吗?

是的,此时节点D只不过从链表中被移除了而已.在C++中,最好手动释放这个D节点和这块内存.

其他语言(如java,python)有自己的内存回收机制,就不用手动释放了

2.添加节点:

可以看出链表的添加和删除都是时间复杂度为为O(1)的操作,不会影响其他节点,但是要注意,删除或者添加某个节点的前提是找到操作节点的上一个节点,而查找前一个节点的时间复杂度是O(n)

性能分析:

把链表的特性和数组特性进行对比:

	插入/删除(时间复杂度)	查询(时间复杂度)	使用场景
数组	O(n)	O(1)	数据量固定,查询频繁,较小增删
链表	O(1)	O(n)	数据量不固定,频繁增删,较小查询

在定义数组的时候,长度是固定的,如果想改动数组的长度,则需要重新定义一个新的数组

而链表的长度可以是不固定的,并且可以动态增删,适合数据量不固定,增删频繁,较少查询的场景

题目:leetcode203.移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/description

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

列表中的节点数目在范围 [0, 10⁴] 内
1 <= Node.val <= 50
0 <= val <= 50

再来看一下删除元素的操作,删除元素就是让节点的next指针直接指向下一个节点的下一个节点.因为单链表的特殊性,所以需要找到操作节点的前一个节点,刚刚删除的是链表中的第二个和第四个节点,如果删除的是头节点,那么该怎么办呢?

这里涉及如下两种链表操作方式:

直接使用原来的链表执行删除操作
设置一个虚拟头节点在执行删除操作

第一种:

删除头节点和删除其他节点的操作是不一样的,因为链表的其他节点都是通过上一个节点来删除当前节点的,而头节点没有上一个节点

那么如何删除头节点呢?其实只要将头节点向后移一位就可以了,这样就从链表中删除了一个头节点

因为删除头节点和删除其他节点的逻辑不一样,所以需要一段单独的一段逻辑来处理删除头节点的情况

代码:

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 Soultion
    {
    public :
        ListNode *removeElements(ListNode *head, int val)
            {
                //删除头节点
                while (head != nullptr && head->val == val)
                    {
                        ListNode *tmp = head;
                        head = head->next;
                        delete tmp;
                    }
                //删除非头节点
                ListNode *cur = head;
                while (cur != nullptr && cur->next != nullptr)
                    {
                        if (cur->next->val == val)
                            {
                                ListNode *tmp = cur->next;
                                cur->next = cur->next->next;
                                delete tmp;
                            } else
                            {
                                cur = cur->next;
                            }
                    }
            }
    };

同样的,我们可以用一个同一个逻辑来删除链表的节点

其实可以设置一个虚拟头节点,这样原链表的所有节点就都可以按照相同的规则来删除了:

这里给链表添加了一个虚拟头节点并将其设为新的头节点,此时删除这个旧的头节点(元素1)的方式就和其他节点方式一样了

在题目中,返回头结点时,别忘了dummyNode才是新的头节点

代码:

struct ListNode
    {
        int val;
        ListNode *next;

        ListNode() : val(0), next(nullptr)
            {}

        explicit ListNode(int x) : val(x), next(nullptr)
            {}

        [[maybe_unused]] ListNode(int x, ListNode *next) : val(x), next(next)
            {}
    };


class [[maybe_unused]] Soultion
    {
    public :
        [[maybe_unused]] static ListNode *removeElements(ListNode *head, int val)
            {
                auto dummyHead = new ListNode(0);
                dummyHead->next = head;
                ListNode *cur = dummyHead;
                while (cur->next != nullptr)
                    {
                        if (cur->next->val == val)
                            {
                                ListNode *tmp = cur->next;
                                cur->next = cur->next->next;
                                delete tmp;
                            } else
                            {
                                cur = cur->next;
                            }
                    }
                head = dummyHead->next;
                delete dummyHead;
                return head;
            }
    };

题目：leetcode707.设计链表

https://leetcode.cn/problems/design-linked-list/description

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]

输出
[null, null, null, null, 2, null, 3]

解释 MyLinkedList myLinkedList = new MyLinkedList();

myLinkedList.addAtHead(1);

myLinkedList.addAtTail(3);

myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3

myLinkedList.get(1);// 返回 2

myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3

myLinkedList.get(1); // 返回 3

提示：

0 <= index, val <= 1000
请不要使用内置的 LinkedList 库。
调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

代码:

class [[maybe_unused]] MylinkedList
    {
        struct LinkedNode
            {
                int val;
                LinkedNode *next;

                explicit LinkedNode(int val) : val(val), next(nullptr)
                    {}
            };

        MylinkedList()
            {
                _size = 0;
                _dummyhead = new LinkedNode(0);
            }

        [[maybe_unused]] int get(int index)
            {
                if (index > (_size - 1) || index < 0)
                    return -1;
                LinkedNode *cur = _dummyhead->next;
                while (index--)
                    cur = cur->next;
                return cur->val;
            }

        [[maybe_unused]] void addAtHead(int val)
            {
                auto *newNode = new LinkedNode(val);
                newNode->next = _dummyhead->next;
                _dummyhead->next = newNode;
                _size++;
            }

        [[maybe_unused]] void addAtTail(int val)
            {
                auto *newNode = new LinkedNode(val);
                LinkedNode *cur = _dummyhead;
                while (cur->next != nullptr)
                    cur = cur->next;
                cur->next = newNode;
                _size++;
            }

        [[maybe_unused]] void addAtIndex(int index, int val)
            {
                if (index > _size)
                    return;
                auto *newNode = new LinkedNode(val);
                LinkedNode *cur = _dummyhead;
                while (index--)
                    cur = cur->next;
                newNode->next = cur->next;
                cur->next = newNode;
                _size++;
            }

        [[maybe_unused]] void deleteAtIndex(int index)
            {
                if (index >= _size || index < 0)
                    return;
                LinkedNode *cur = _dummyhead;
                while (index--)
                    cur = cur->next;
                LinkedNode *tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
                _size--;
            }

        [[maybe_unused]] void printLinkedList()
            {
                LinkedNode *cur = _dummyhead;
                while (cur->next != nullptr)
                    {
                        cout << cur->next->val << " ";
                        cur = cur->next;
                    }
                cout << endl;
            }

    private:
        int _size;
        LinkedNode *_dummyhead;
    };

题目:leetcode206.反转链表

https://leetcode.cn/problems/reverse-linked-list/description

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

思路:如果定义了一个新的链表实现链表元素的反转,则是对内存空间的浪费.其实只需要改变链表的next指针的指向,直接将链表反转即可,而不用重新定义一个新的链表

1.双指针法:

首先定义一个cur指针,指向头节点,再定义一个pre指针,初始化为NULL,接下来就要开始反转了

首先使用tmp指针保存cur->next节点,接下来要改变cur->next的指向,将cur->next指向pre

然后循环上面的逻辑,继续移动pre和cur指针.

最后cur指针指向了NULL,循环结束,链表也反转完毕.此时我们返回pre指针即可,pre指针指向了新的头节点

代码:

class [[maybe_unused]] Soultion
    {
    public:
        struct ListNode
            {
                [[maybe_unused]] int val;
                ListNode *next;

                ListNode() : val(0), next(nullptr)
                    {}
            };

        [[maybe_unused]] static ListNode *reverseList(ListNode *head)
            {
                ListNode *pre = nullptr;
                ListNode *cur = head;
                while (cur)
                    {
                        ListNode *temp = cur->next;
                        cur->next = pre;
                        pre = cur;
                        cur = temp;
                    }
                return pre;
            }
    };

2.递归法:

递归法相对抽象一些,其实和双指针法是一样的,同样是当cur为空的时候循环结束,不断将cur指向pre的过程.

关键是初始化的地方,可以看出双指针法中初始化cur=head,pre=NULL.在递归法中可以看出初始化的逻辑也是一样的,只不过写法变了

class [[maybe_unused]] Soultion
    {
    public:
        struct ListNode
            {
                [[maybe_unused]] int val;
                ListNode *next;

                ListNode() : val(0), next(nullptr)
                    {}
            };

        ListNode *reserveList(ListNode *pre, ListNode *cur)
            {
                if (cur == nullptr)
                    return pre;
                ListNode *temp = cur->next;
                cur->next = pre;
                return reserveList(cur, temp);
            }

        [[maybe_unused]] ListNode *reverseList(ListNode *head)
            {
                return reserveList(nullptr, head);
            }
    };

题目:leetcode19.删除链表的倒数第n个节点

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

思路:本题是双指针法的经典应用,如果要删除倒数第n个节点,则让fast移动n步,然后让fast和slow同时移动,直到fast指向链表末尾,删除slow所指向的节点就可以了.

删除链表中的倒数第n个节点分为如下几步:

1.推荐使用虚拟头节点,这样方便处理删除实际头结点的逻辑

2.定义fast指针和slow指针,初始值为虚拟头节点(dummyHead),删除倒数第n个节点.例如n为3:

3.fast先移动n+1步,为什么是n+1呢?因为只有这样,fast和slow同时移动时slow才能指向删除节点的上一个节点(方便做删除操作)

4.fast和slow同时移动,直到fast指向末尾(NULL)

5.删除slow指向的下一个节点

代码:

class [[maybe_unused]] Solution
    {
        struct ListNode
            {
                [[maybe_unused]] int val;
                ListNode *next;

                ListNode() : val(0), next(nullptr)
                    {}

                explicit ListNode(int x) : val(x), next(nullptr)
                    {}
            };

        [[maybe_unused]] static ListNode *removeNthFromEnd(ListNode *head, int n)
            {
                auto *dummyHead = new ListNode(0);
                dummyHead->next = head;
                ListNode *slow = dummyHead;
                ListNode *fast = dummyHead;
                while (n-- && fast != nullptr)
                    {
                        fast = fast->next;
                    }
                fast = fast->next;
                while (fast != nullptr)
                    {
                        slow = slow->next;
                        fast = fast->next;
                    }
                return dummyHead->next;
            }
    };

发表评论 取消回复

发表评论取消回复