【Java版oj】反转链表

浅浅的花香味﹌ 2024-04-03 13:10 67阅读 0赞

**目录**

一、原题再现

二、 问题分析

三、完整代码

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

> ## 一、原题再现 ##
> 
> [206. 反转链表][206.]
> 
> 难度简单2802
> 
> 给你单链表的头节点 `head` ，请你反转链表，并返回反转后的链表。
> 
> **示例 1：**
> 
> ![e827480614f5990eddbe9138cc78ff05.jpeg][]
> 
>     输入：head = [1,2,3,4,5]
>     输出：[5,4,3,2,1]
> 
> **示例 2：**
> 
> ![79d85a13cf56a9c200eabb1daa1af250.jpeg][]
> 
>     输入：head = [1,2]
>     输出：[2,1]
> 
> **示例 3：**
> 
>     输入：head = []
>     输出：[]
> 
> **提示：**
> 
>  *  链表中节点的数目范围是 `[0, 5000]`
>  *  `-5000 <= Node.val <= 5000`

> ## 二、 问题分析 ##
> 
> 链表反转，其主要做法是改变所有结点的指向位置。因此需要定义一个当前节点cur以及cur节点的前一个节点pre、后一个节点curNext。不断水平移动结点pre和cur的位置，使原本结点cur的指向现在指向结点pre，再将结点pre、cur往后平移一个结点位置，即pre=cur；cur=cur.next;依次遍历完所有节点，就可以完成反转了。
> 
> 其中需要注意的是：当改变当前节点cur的指向时，如果我们不做处理，就无法找到当前结点的下一个结点即无法完成遍历。因此需要在改变cur结点指向之前保存cur结点的下一个结点。ListNode curNext=cur;cur=curNext;
> 
> ![57a5013f5c8940a597ad4ee27a98ed78.png][]

> ## 三、完整代码 ##
> 
>     /**
>      * Definition for singly-linked list.
>      * public class ListNode {
>      *     int val;
>      *     ListNode next;
>      *     ListNode() {}
>      *     ListNode(int val) { this.val = val; }
>      *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
>      * }
>      */
>     class Solution {
>         public ListNode reverseList(ListNode head) {
>             ListNode cur=head;
>             ListNode pre=null;
>             while(cur!=null){
>                 ListNode curNext=cur.next;
>                 cur.next=pre;
>                 pre=cur;
>                 cur=curNext;
>             }
>             return pre;
>         }
>     }
> 
> ![d8e967833ff24d5793745cd857239621.png][]

![c7f3bd22d2ae4a18a3211b997657eb7f.png][]

[206.]: https://leetcode.cn/problems/reverse-linked-list/
[e827480614f5990eddbe9138cc78ff05.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/ebb11c486f344b47a1819761d87e3f05.jpeg
[79d85a13cf56a9c200eabb1daa1af250.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/077b52d8de0d43beaf2ec4c0bcf82b12.jpeg
[57a5013f5c8940a597ad4ee27a98ed78.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/f8cdf81fcc6342d5ae113878af373146.png
[d8e967833ff24d5793745cd857239621.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/07ff139313c34388bb8945a7268ed4e6.png
[c7f3bd22d2ae4a18a3211b997657eb7f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/ed85de6bc799470e801c5ef189396436.png