[数据结构与算法]【力扣】C语言实现反转链表

目录

一、目的

二、方法

方法一：分隔头插

方法二：逆转箭头

一、目的

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

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

二、方法

方法一：分隔头插

1.将第一个结点和其他结点分隔开，将分隔下来的链表分别进行头插，实现逆转

struct ListNode* reverseList(struct ListNode* head){//这里的head指的是第一个结点
    if(head==NULL||head->next==NULL){
        return head;
    }
    struct ListNode *p=head;
    struct ListNode *q=p->next;
    p->next=NULL;//分隔
    while(q!=NULL){
        p=q;
        q=q->next;
        p->next=head;
        head=p;//改变head的位置
        
    }
    return head;

}

方法二：逆转箭头

1.整个过程相当于逆向了箭头的指向

2.但是必须事先将q的下一个结点值记录下来，要不然会发生内存泄漏

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* p = NULL;
    struct ListNode* q = head;
    while (q) {
        struct ListNode* next = q->next;//必须存下curr下一个结点的值，要不然curr->next指向prev时，就会丢失掉剩下的结点
        q->next = p;
        p = q;
        q = next;
    }
    return p;
}