【数据结构】1.链表

系列文章

【基础算法】1.排序及二分

【基础算法】2.高精度&前缀和与差分

【基础算法】3.双指针、位运算、离散化、区间合并

【数据结构】1.链表

【基础算法】习题课1

系列代码

GALA-Lin/Algorithm: CSDN基础算法系列配套代码

一、链表

void resverse()

1. Node* prev = NULL;
   Node* current = head;
   Node* next = NULL;
   

   • prev：用于存储链表中当前节点的前一个节点。初始值为NULL，因为链表的最后一个节点的next指针应该指向NULL。
   • current：指向链表的头节点head，开始时从头节点开始反转。
   • next：用于存储链表中当前节点的下一个节点。初始值为NULL。

2. 遍历链表并反转每个节点的next指针

   while (current != NULL) {
       next = current->next; // 保存当前节点的下一个节点
       current->next = prev; // 将当前节点的next指针指向prev，实现反转
       prev = current;         // 将prev移动到当前节点
       current = next;       // 将current移动到下一个节点
   }
   

   • 这个循环会一直执行，直到current指针变为NULL（即遍历到链表的末尾）。
   • 在每次循环中，首先保存当前节点的下一个节点到next，然后将当前节点的next指针指向prev，接着将prev和current指针依次向后移动一个节点。

3. 更新头节点

   head = prev;
   

   • 当循环结束后，prev指针会指向原本链表的最后一个节点，这是反转后的新头节点。因此，将head指针更新为prev，完成链表的反转。
     完整代码：

    void resverse(){
        Node* prev=NULL;
        Node* current=head;
        Node* next=NULL;
        while(current!=NULL){
            next=current->next;
            current->next=prev;
            prev=current;
            current=next;
        }
        head=prev;
    }

二、数组实现链表