算法详解 | 反转单向链表基础版

﹏ヽ暗。殇╰゛Y 2022-10-05 04:45 173阅读 0赞

# 算法详解 | 反转单向链表基础版 #

> 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

从定义可以知道，链表的每个元素实际上在内存中并不是连续，只是逻辑上看起来是连续。

## Leetcode题目 ##

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

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

限制：

`0 <= 节点个数 <= 5000`

## 解题思路 ##

因为我们不知道链表的元素具体位置，所以要对单向链表进行排序，只能从头开始遍历，确定头部节点的位置是关键。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center]

从上图可以看到，我们需要做的是使反转后头部节点从1变成5而尾部节点从5变成1，由于是整条链进行反转，反转后的尾部肯定就是目前的头部节点。这时候尾部节点已经是已知条件，只需要确定反转后的头部节点。对链表前后两个节点换位，明显需要两个元素配合，这里需要两个指针分别定义为`pre`和`curr`。但是这两个指针是需要挪动位置的，必须有一个指针知道下一个节点的位置，因此我们还需要一个临时指针`tmp`去辅助。

Pre = Head;
    Cur = Head.next;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 1]

接下来我们对解题步骤进行拆分:

### 步骤1 ###

由于当前节点head，我们已经知道它反转后肯定会作为尾部节点，因此我们可以直接把它next指针指向null

pre.next = null

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 2]

### 步骤2 ###

把cur对应的节点2)指向前一个节点(1)

Cur.next = Pre

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 3]

### 步骤3 ###

把Pre和Cur指针移动到下一个节点，移动后Per和Cur分别指向2，3节点

Cur.next = Tmp;
    Pre = Cur;
    Cur = Tmp;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 4]

### 步骤4 ###

重复前面的步骤，把Cur指针对应的节点(3)指向前一个节点(2)

Cur.next = Pre

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 5]

### 步骤5 ###

接下来Pre，Cur指针继续前移，这时候又需要Tmp指针临时辅助，前移后Pre指针对应节点(3)，Cur指针对应节点4

Cur.next = Tmp;
    Pre = Cur;
    Cur = Tmp;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 6]

### 步骤6 ###

这时候，继续重复前面的操作，把Cur指针对应的节点(4)指向上一个节点(3)

Cur.next = Pre

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 7]

### 步骤7 ###

接下来Pre，Cur指针继续前移，这时候又需要Tmp指针临时辅助，前移后Pre指针对应节点(4)，Cur指针对应节点5

Cur.next = Tmp;
    Pre = Cur;
    Cur = Tmp;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 8]

### 步骤8 ###

这时候，继续重复前面的操作，把Cur指针对应的节点(5)指向上一个节点(4)

Cur.next = Pre

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 9]

### 步骤9 ###

接下来Pre，Cur指针继续前移，这时候又需要Tmp指针临时辅助，前移后Pre指针对应节点(5)，Cur指针对应null，这时候你会发现，我们已经将整条链表反转，并且Pre指针对应的就是需要返回的Head节点，这时候直接return Pre指针饮用的节点即可

Cur.next = Tmp;Pre = Cur;Cur = Tmp;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 10]

## 结论 ##

我们根据上面的推演，可以得出以下模型：

当Cur移动到null的时候，此时Pre指针指向的就是head节点

while(Cur!=null){   Cur.next=Tmp;  Cur.next=Pre;  Pre = Cur;  Cur = Tmp;} return Pre;

### 特殊情况 ###

我们还需要考虑的是当head 是null或者链表元素只有一个的情况，尝试套入模型是否可行，如果不可行则特殊处理。很明显当传进来的Head是null，需要特殊处理  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 11]

## 解决方案 ##

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

执行结果如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 12]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center]: /images/20221005/8ccd98bfc2e84e5eb55ced73d71395c4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221005/ad3f31167c3f41708ec29dcaf182842a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221005/237f3102a8f04e23b3c53dcc31741295.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221005/23e3f01b5b774d64a3d964e0c8d81b8e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221005/f231c7fe230647249399bfceacc523b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221005/f293fbd0eb4342e798cdc76ddd184810.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221005/b78c5c75b63d4b38ad8ddabe33768ef8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221005/243c1682a50244a484b666e703fc183c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221005/97232da06a584eb4b1b9de310819211e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221005/591a3f4372a34308a35f7185baf38b88.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221005/0a9ab4b8147c4167bb7038b9e904c94b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221005/ae33af82441345db8e408b18263e0e64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0V2YW5fTGV1bmc_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221005/59debe9001af4089ac799bf8f29a6593.png