数据结构与算法之单链表的关系_数据结构链表删除节点

数据结构与算法之单链表

链表概念

链表是一种通过指针串联起来的线性结构，每一个节点由两部分组成，存放数据的部分称为数据域；存放指针的部分被称为指针域，指针域存放指向下一个节点的指针(最后一个节点的指针域指向空指针)。
结点
单个结点图如下：

节点结构c++代码

struct ListNode { 
    int val; ListNode *next; ListNode(int x) : val(x), next(NULL) { 
   } }; 

链表在内存中的存贮方式

数组元素在内存空间上是连续分布的，而链表的节点在内存空间上不是连续分布的，链表通过指针域的指针来连接分布在内存中的各个节点。
单链表如下所示：

注意：
1、链表的插入、删除结点的时间复杂度为O(1)。
2、访问链表中的某个结点的时间复杂度为O(n)。

关于链表的各种操作

链表类

说明：类中使用虚头节点是使得删除(插入)头节点与删除(插入)其它节点代码一致，另外假设头节点对应索引为0

struct ListNode { 
    int val; ListNode *next; ListNode(int x) : val(x), next(NULL) { 
   } }; class MyLinkedList { 
    public: MyLinkedList():_dummy(new ListNode(0)), _size(0){ 
    } ~MyLinkedList(){ 
    clear(); delete _dummy; _dummy = nullptr; } int get(int index)const; bool insertNode(int index, int val); bool deletNode(int index); void clear(); void reverse(); int midNode(); private: ListNode *_dummy; //虚头结点 int _size; //链表中结点个数 }; 

1、查找指定索引处的元素

假设头节点对应索引为0,其他节点索引依次递增，并且索引无效将返回-1

int MyLinkedList::get(int index)const{ 
    if(index < 0 || index >= _size) return -1; ListNode *cur = _dummy->next; while(index){ 
    cur = cur->next; --index; } return cur->val; } 

2、在指定索引处插入一个节点

例如在索引2处插入一个值为6的节点
插入前：

插入后

在进行插入元素操作时我们需要找到该位置的前一个位置的节点，然后再进行插入

bool MyLinkedList::insertNode(int index, int val){ 
    if(index < 0 || index > _size) return false; ListNode *pre = _dummy; ListNode *cur = _dummy->next; while(index){ 
    pre = cur; cur = cur->next; --index; } ListNode *newNode = new ListNode(val); pre->next = newNode; newNode->next = cur->next; ++_size; return true; } 

3、删除指定索引处的节点

例如要删除索引2处的节点
删除前：

删除后：

bool MyLinkedList::deletNode(int index){ 
    if(index < 0 || index >= _size) return false; ListNode *pre = _dummy; ListNode *cur = _dummy->next; while(index){ 
    pre = cur; cur = cur->next; --index; } pre->next = cur->next; delete cur; --_size; return true; } 

4、清空链表

void MyLinkedList::clear(){ 
    ListNode *cur = _dummy->next; while(cur != nullptr){ 
    ListNode *node = cur->next; delete cur; cur = node; } _dummy->next = nullptr; _size = 0; } 

5、翻转链表

void MyLinkedList::reverse(){ 
    if(_size == 0) return _dummy; ListNode* pre = nullptr; ListNode* cur = _dummy; while(cur != nullptr){ 
    ListNode* node = cur->next; cur->next = pre; pre = cur; cur = node; } _dummy->next = pre; } 

6、找链表的中间节点

利用双指针实现：定义一个慢指针slow，每次走一个节点；定义一个快指针fast，每次走两个节点，slow和fast都从头节点出发，当fast->next 为空指针或者fast->next->next为空指针时，slow指向的就是中间节点

int MyLinkedList::midNode(){ 
    ListNode* slow = _dummy->next; ListNode* fast = _dummy->next; while(fast->next != nullptr && fast->next->next != nullptr){ 
    slow = slow->next; fast = fast->next->next; } return slow->val; } 

7、判断链表是否有环

该函数适合没有虚头节点的链表，所以不作为成员函数

利用双指来实现：定义一个慢指针slow，每次走一个节点；定义一个快指针每次走两个节点，这两指针都从头节点出发，若存在环则最终这两个指针会相遇，否则没有环

bool circle(ListNode* head){ 
    ListNode* slow = head; ListNode* fast = head; while(fast->next != nullptr && fast->next->next != nullptr){ 
    slow = slow->next; fast = fast->next->next; if(fast == slow) return true; } return false; } 

8、若有环如何找环的入口呢？

说明：该函数适合没有虚头节点的链表，所以不作为成员函数

假设头结点到环形入口的节点数为x，入口节点到快慢指针相遇节点的节点数为y，相遇点到入口的节点数为z。在这里slow指针走一个节点，fast指针走两个节点。
当两个指针相遇时，slow指针走过的节点数为：x+y。fast指针走过的节点数为：x+y + n(y + z)，其中n表示相遇前fast指针走过的圈数。slow指针走一个节点，fast指针走两个节点，则 2(x+y) = x+y + n(y + z)。最终x = n(y + z) - y = (n - 1)(y + z) + z，在这里n至少为1。
当n = 1时，x = z，于是我们可以在快慢指针相遇时，在设置一个从头节点出发的指针cur，让cur和slow同时运动，最终cur和slow的相遇点即为环入口。

ListNode* findCircleEnter(ListNode* head){ 
    ListNode* slow = head; ListNode* fast = head; while(fast->next != nullptr && fast->next->next != nullptr){ 
    slow = slow->next; fast = fast->next->next; if(fast == slow){ 
    ListNode* cur = head; while(cur != slow){ 
    cur = cur->next; slow = slow->next; } return cur; } } return nullptr; } 

总结

1、链表的插入和删除的时间复杂度为O(1)。
2、访问链表中某个节点的时间复杂度为O(n)。