LeetCode 图解 | 206.反转链表

太过爱你忘了你带给我的痛 2023-07-07 05:38 3阅读 0赞

点击上方蓝字设为星标![format_png][]

下面开始今天的学习～

![format_png 1][]

今天分享的题目来源于 LeetCode 上第 206 号问题：反转链表。这道题目经常出现在算法面试中的笔试环节。

### 题目描述 ###

反转一个单链表。

**示例:**

输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL

### 题目解析 ###

在原链表之前建立一个空的节点 pre，然后从头节点 cur 开始，先保存 `cur->next` 为 next ，将 cur 的 next 节点变为 pre，pre 移到 cur，cur 移动到 next。

重复此操作直到 cur 成为末节点为止。

### 动画理解 ###

### 参考代码 ###

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode reverseList(ListNode head) {
            ListNode cur = head, pre = null;
            while (cur != null) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
           return pre;
        }
    }

### 复杂度分析 ###

*  **时间复杂度**：O(n)。
 *  **空间复杂度**：O(1)。

### 相关题目推荐 ###

*  LeetCode 26：删除排序数组中的重复项
 *  LeetCode 203：移除链表元素

**END**

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

![format_png 2][]

● [答应我，别再if/else走天下了可以吗][if_else]

[● ][Link 1][如何利用寒假的时间来准备2020年的蓝桥杯?][2020]

● [给大家推荐一款软件][Link 2]

● [关于计算机读研的小建议][Link 3]

![format_png 3][]

原创不易，点“在看”你懂得

![format_png 4][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9pY0hvZXJLTzNOakxHa0wzSmljWnh6WlVsTVBXYU9FVXRpYVZ5RHQ1QU9hSUpOa0xhbHRYT1lSaWFHU2J5aWJneFFzVkxSYXo5SnhmTjZLVkJtU05GYkZlNkx3LzY0MA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9taWFabTA1NHZVaWJ1Mlo1T0d1SXpidXdUaWFpYmlhNWxNU3pJM29iS1B4SDlLeGtTeTdQM3NkNjlpY0dUR3kxVGVXUXIzTjIxUVNjcnJpYmFIRGJYRmJrd1lnOXcvNjQw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9wNldsMkxETVFsSEM2cERYeVFSYVdqbFdSNVBJaHVrSVVHVjFuZks2SDlxdEhab3huWHRWZGV6dG9GZXhrYWV2dWRtWjFNYlY5cVdOWlRYaWFvcEx5b1EvNjQw?x-oss-process=image/format,png
[if_else]: https://blog.csdn.net/kexuanxiu1163/article/details/104140332
[Link 1]: http://mp.weixin.qq.com/s?__biz=Mzg2MzE5MjMxNQ%3D%3D&chksm=ce7ef418f9097d0e01bfe9410a9e40e9f4337c835c87e28332e6a8d8fd8b91b4794164f4c1a1&idx=1&mid=2247491980&scene=21&sn=5ef03c0108a5730fa28e492ec77e22d9#wechat_redirect
[2020]: https://blog.csdn.net/kexuanxiu1163/article/details/104140333
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e6038cd79e92ec7f54e62aaf535c402eed0be07e97d1fdbced663280d2dccdda047ee099c&idx=1&mid=2247487417&scene=21&sn=13d97404f7f5700bb901171e4d9f91e4#wechat_redirect
[Link 3]: https://blog.csdn.net/kexuanxiu1163/article/details/104078939
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJ1Mlo1T0d1SXpidXdUaWFpYmlhNWxNU3pJSnhabmliTURvdkhpY0lOZ2N3RWtKZXhlVVZkQTZGMVJNMzlGTVJaajE2U3JwOVFtRURpYXZhZmliQS82NDA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jNmdxbWhXaWFmeXI5djFSblJIZGdiRTlWTzljY2pWU0FuOGpxUXBoeUxKbDU5N1JzOUJ6RVViQlIwQUdmSmZ2a3pMOXJ1cWtUbVBBWHIyOXRISWNwRFEvNjQw?x-oss-process=image/format,png