Leetcode 图解反转链表

骑猪看日落 2022-04-23 13:24 184阅读 0赞

问题描述

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5NTUwMA_size_16_color_FFFFFF_t_70][]

先上代码：

/\*\*  
 \* 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 pre = null, next = null, cur = head;  
        while(cur != null) \{  
            //取出当前节点的下一个节点  
            next = cur.next;  
            //令这个节点的next为前一个节点  
            cur.next = pre;  
            //pre游标向后移动  
            pre = cur;  
            //cur游标向后移动  
            cur = next;  
        \}  
        return pre;  
    \}  
\}

解析：

重点在于while循环的四行，这里设置了三个游标，每次循环都把当前游标的next指针反转，当cur移到链表末端时，即完成反转。

初始状态如下

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5NTUwMA_size_16_color_FFFFFF_t_70 1][]

第一次循环，执行完前两行之后：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5NTUwMA_size_16_color_FFFFFF_t_70 2][]

执行完第一遍循环的状态：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5NTUwMA_size_16_color_FFFFFF_t_70 3][]

以此类推，完成第二遍循环时的状态：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5NTUwMA_size_16_color_FFFFFF_t_70 4][]

时间复杂度：

这个算法只需要扫描一遍即可完成链表反转，时间复杂度是O(n)。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5NTUwMA_size_16_color_FFFFFF_t_70]: /images/20220317/50a1bc3c80e44719b7ecb8c002e914fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5NTUwMA_size_16_color_FFFFFF_t_70 1]: /images/20220317/b9ededf73d094097800fefdc122b20c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5NTUwMA_size_16_color_FFFFFF_t_70 2]: /images/20220317/3be400ff1e7d4cbaaea36a07d6b269a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5NTUwMA_size_16_color_FFFFFF_t_70 3]: /images/20220317/ee0338620d5840a0bd819464356780ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5NTUwMA_size_16_color_FFFFFF_t_70 4]: /images/20220317/2c82d94a188640158741b49327da2f7c.png