【链表OJ题 1】反转链表

Love The Way You Lie 2023-09-27 18:23 75阅读 0赞

**目录**

题目来源：

代码实现

1、方法一

1.1分析

2、方法二

2.1 分析

--------------------

## 题目来源： ##

[力扣][Link 1]

**题目描述：**

![c60d2faefe870abfc1bd8af09f8a5ba8.png][]

## 代码实现 ##

### 1、方法一 ###

struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode* prev = NULL, * cur = head;
        while (cur)
        {
            struct ListNode* next = cur->next;
            //头插
            cur->next = prev;
            prev = cur;
            //迭代
            cur = next;
        }
        return prev;
    }

#### 1.1分析 ####

![f2f3c5ac9adee0c3c5c8caf9ca671286.png][]

方法一是头插法。

创建三个结构体指针变量：prev、cur、next。

**我们先置空 prev，将头指针 head 存放在 cur 中，next 存放 cur 的 next。第一次 cur 的 next 赋值为 prev 就是空，next 指向 cur的next，prev 指向当前的 cur。不断循环，当 cur 为空时就将整个链表反转完成了。**

**重点：**

1.循环：next = cur->next; cur->next = prev; prev = cur; cur = next; 这个循环体的顺序是不可以交换的。 循环条件应该是 cur != NULL 时就进入循环，等于 NULL 的话就说明全部的结点头插已经完成了。

2.返回值：因为是头插，prev 一直指向头结点，所以返回 prev。return prev;

![192b89518e717e356202e6ede684440d.png][]

### 2、方法二 ###

struct ListNode* reverseList(struct ListNode* head) {
        if(head == NULL)
            return NULL;
    
        struct ListNode* n1 = NULL, * n2 = head, * n3 = n2->next;
        while (n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if(n2 != NULL)
                n3 = n3->next;
        }
        return n1;
    }

#### 2.1 分析 ####

![e924b54d3bfd1b613f1dc99fea50239c.png][]

方法二是逆置法，将开始向右的箭头改为向左就逆置成功了。

创建三个结构体指针变量：n1、n2、n3。

**先置空 n1 ，将 head 存放在 n2 中，n3 保存 n2的next。将 n2的next 指向 n1，这样就可以让头结点的next指向空；然后将 n1 赋值为 n2；再将 n2 赋值为 n3；n2 如果指向的结点不为空，n3 就在自己的基础上再往后走一步。**

**重点：**

1.如果原链表为空，就返回NULL；

2.循环：n2->next = n1; n1 = n2; n2 = n3; n3 = n3->next; 这个循环体的顺序是不可以交换的。以我们的图来看，当 n2 为空的时候循环停止，因此循环条件为 n2(n2 != NULL 与 n2 是一样的)。

3.返回值：我们的 n2 走到 NULL 的时候，n1 正好就指向了原链表的尾结点，因为是逆置，所以返回的就是尾结点。return n1；

4**.**循环体中，最后一次改变 n3 时 n3 已经是空了，再让 n3 = n3 ->next, 会出现空指针问题，因此我们在 n3 的改变上加一个判断条件 n3 != NULL，如果为空 n3 就不再往后移了。

![b98ff4a5fe92669896c1f072e3968711.png][]

[Link 1]: https://leetcode.cn/problems/reverse-linked-list/
[c60d2faefe870abfc1bd8af09f8a5ba8.png]: https://img-blog.csdnimg.cn/img_convert/c60d2faefe870abfc1bd8af09f8a5ba8.png
[f2f3c5ac9adee0c3c5c8caf9ca671286.png]: https://img-blog.csdnimg.cn/img_convert/f2f3c5ac9adee0c3c5c8caf9ca671286.png
[192b89518e717e356202e6ede684440d.png]: https://img-blog.csdnimg.cn/img_convert/192b89518e717e356202e6ede684440d.png
[e924b54d3bfd1b613f1dc99fea50239c.png]: https://img-blog.csdnimg.cn/img_convert/e924b54d3bfd1b613f1dc99fea50239c.png
[b98ff4a5fe92669896c1f072e3968711.png]: https://img-blog.csdnimg.cn/img_convert/b98ff4a5fe92669896c1f072e3968711.png