【数据结构OJ题】反转链表

电玩女神 2023-09-27 18:22 86阅读 0赞

**反转链表**

原题链接：[https://leetcode.cn/problems/reverse-linked-list/][https_leetcode.cn_problems_reverse-linked-list]

![9acf045218384e36803e6a43901215b9.png][]

**方法一：**改变链表中指针的指向

首先定义三个指针 n1 n2 n3 ,指向位置如下：

![d412d696895c49d49596ec92f035b963.png][]

然后就是一个循环的过程了，每次将n2的next指向n1,n2赋给n3,n3指向n3的next  ，就可以实现n1,n2,n3不断地向后移动，如下图：

![1681a2e900234690944838b79baf5bc3.png][]

注意循环终止的条件 n2为空指针的时候才终止，同时当**n3**为空指针的时候，不能让n3->next指向空

上面的方法是针对链表不是空链表而设计的，如果是空链表，程序就会出错，此时可以直接返回一个空指针即可

代码：

struct ListNode* reverseList(struct ListNode* head)
    {
        if(head==NULL) //如果链表为空，直接返回空指针
        {
            return NULL;
        }
        struct ListNode*n1=NULL,*n2=head,*n3=head->next;
        while(n2)
        {
            n2->next=n1;
            n1=n2;
            n2=n3;
            if(n3!=NULL)
            {
                n3=n3->next;
            }
        }
        return n1;
    }

**方法二：每次移动链表的数据**

这种方法也需要用到三个指针变量，具体步骤和上面类似，如下图：

![97fb4da709cf406ab6d47e828324b3c4.png][]

**代码：**

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;
    }

[https_leetcode.cn_problems_reverse-linked-list]: https://leetcode.cn/problems/reverse-linked-list/
[9acf045218384e36803e6a43901215b9.png]: https://img-blog.csdnimg.cn/9acf045218384e36803e6a43901215b9.png
[d412d696895c49d49596ec92f035b963.png]: https://img-blog.csdnimg.cn/d412d696895c49d49596ec92f035b963.png
[1681a2e900234690944838b79baf5bc3.png]: https://img-blog.csdnimg.cn/1681a2e900234690944838b79baf5bc3.png
[97fb4da709cf406ab6d47e828324b3c4.png]: https://img-blog.csdnimg.cn/97fb4da709cf406ab6d47e828324b3c4.png