您现在的位置是:首页 >技术交流 >单链表OJ题:LeetCode--206.反转链表网站首页技术交流

单链表OJ题:LeetCode--206.反转链表

stackY、 2024-06-08 00:00:02
简介单链表OJ题:LeetCode--206.反转链表

朋友们、伙计们,我们又见面了,今天给大家带来的是LeetCode中206题:反转链表

数 据 结 构:数据结构专栏

作          者:stackY、

C  语   言  :C语言专栏

LeetCode :LeetCode刷题训练营

LeetCode--206.反转链表: https://leetcode.cn/problems/reverse-linked-list/description/

目录

1.题目介绍 

2.实例演示 

3.题解思路 

3.1改变结点的指向 

3.2头插法 


1.题目介绍 

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

  

2.实例演示 

3.题解思路 

反转链表有两种思路:

1.直接改变链表的指向。

2.使用结点直接进行头插。

3.1改变结点的指向 

如果链表为空直接返回NULL,若不为空,先记录头结点(n2)和头结点的下一个位置(n3),然后设置一个指针(n1),先置为NULL,然后将头指针(n2)指向n1,这时头指针就需要向后面后一步,因此需要将n3赋给n2,n2赋给n1,再将n3向后走一步,再让新的头指针(n2)指向新的n1,再往后面走,依次类推,直到遍历完整个链表,这里要注意,如果n3已经为空,那么n3就不能走了,如果n2为空,链表就反转结束。这时n1就变成了新的头,返回n1就可以了。

代码演示:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    //链表为空直接返回
    if(head == NULL)
    {
        return NULL;
    }
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* n3 = head->next; 
    //遍历
    while(n2)
    {
        //改变头结点的指向
        n2->next = n1;

        //更新新的结点
        n1 = n2;
        n2 = n3;
        //n3不为空才可以指向下一个
        if(n3 != NULL)
            n3 = n3->next;
    }
    //返回新的头
    return n1;  
}

3.2头插法 

取结点进行新一轮的头插就比较简单,只需要记录头结点的下一个结点的位置,然后头插,迭代,这里也不需要考虑第一次插入是空指针的问题,直接插入,然后返回新的头。

代码演示:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;

    while(cur)
    {
        //保存头结点的下一个结点
        struct ListNode* next = cur->next;

        //头插
        cur->next = newhead;
        //更新新的头
        newhead = cur;
        
        //迭代
        cur = next;
    }
    return newhead;
}

今天的博客就分享到这里,喜欢的老铁留下你的三连,感谢感谢!我们下期再见!! 

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。