【经典算法面试题一】反转链表的两种解决方法

淩亂°似流年 2022-09-11 14:25 197阅读 0赞

## 类似题目：反转一个单链表 ##

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

### 解法1：迭代 ###

重复某一过程，每一次处理结果作为下一次的初始值，这些初始值类似于状态、每次处理都会改变状态、直至到达最终状态。

**先定义三个变量**  
prev：保存当前节点的上一个节点；将当前节点的next指向上一个节点  
curr：保存当前节点；  
next：提前保存当前节点的下一个节点

**从前往后遍历步骤：**  
1.将当前节点赋值给curr,`curr = head`；初始化prev变量为null  
2.将当前节点的下一个节点指针保存到next变量,`next = curr.next`  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16]  
3.将当前节点（curr）的next指针指向prev变量，`curr.next = prev`  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
4.准备处理下一个节点，将curr赋值给prev变量,`prev = curr`  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
5.将保存下一个节点的next变量赋值给curr变量,`curr = next`，处理下一个节点  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
目前为止完成链表的第一个节点的反转（由于是链表的开头节点，所以next指向null），后面循环重复上面的2，3，4，5步即可通过迭代完成链表的反转，循环的结束条件就是当前节点（curr）为null。

#### 代码实现 ####

public class ReverseListNode {
        
    
    	//定义链表
        static class ListNode{
        
            int val;
            ListNode next;
    
            public ListNode(int val ,ListNode next){
        
                this.val = val;
                this.next = next;
            }
        }
        
    	//使用迭代方式反转
        public static ListNode iterateReverse(ListNode head){
        
            ListNode prev = null,next;
            ListNode curr = head;//定义curr变量并初始化为头节点
            while (curr != null){
        
                next = curr.next;//将当前节点的下一个节点赋值给next
                curr.next = prev;//将上一个节点赋值给当前节点的下一个节点，实现单个节点反转
                prev = curr;//将当前节点赋值给prev
                curr = next;//当前节点变量指向链表下一个节点
            }
            return prev;
        }
    
        public static void main(String[] args){
        
            ListNode node5 = new ListNode(5,null);
            ListNode node4 = new ListNode(4,node5);
            ListNode node3 = new ListNode(3,node4);
            ListNode node2 = new ListNode(2,node3);
            ListNode node1 = new ListNode(1,node2);
            ListNode head = node1;
            while (head != null){
        
                System.out.print(head.val + "---->");
                head = head.next;
            }
            System.out.println();
            ListNode headReverse = iterateReverse(node1);
            while (headReverse != null){
        
                System.out.print(headReverse.val + "---->");
                headReverse = headReverse.next;
            }
    
        }
    }

#### 解法2：递归 ####

以相似的方法重复，通过不断的自调把大问题变成相似的小问题，然后逐一的来解决每个小问题而达到解决大问题目的。

在这道题中小问题就是两个节点之间把指针调换，以此达到反转链表的目的。  
**以 前两个节点为例：**  
要实现第二个节点next指向上一个节点，只需`curr.next.next = curr`（curr表示当前节点）；  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
当前节点的next指向为空，即`curr.next = null`;  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
这样的话就能实现前两个节点的反转，但是又出现一个问题：  
`2---->3`的节点上的指针断开了，2节点后面的链表不见了，这怎么弄。

**从尾节点开始**  
当当前节点（curr）为4时，可以看出`curr.next.next = curr`,即可实现为节点next的反转，如下图：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
当前节点的next指向为空，即`curr.next = null`;如下图：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
从上面的图片可以看出这样就不会出现链表丢失的问题，可行，代码实现如下（具体类请参考上面的代码，此处只贴该实现方法）  
代码如下：

public static ListNode recursion(ListNode head){
        
            //当head为空或是最后一个节点时返回
            if(head == null || head.next == null){
        
                return head;
            }
            //head_new 定义为反转后的头节点变量
            ListNode head_new = recursion(head.next);
            /**
             * 上面递归到最后一个节点时，返回head为5，保存到head_new变量中
             * 而由于调用方法的参数为head.next = 5
             * 所以此处head = 4
             */
            head.next.next = head;
            head.next = null;
            
            //最后返回头节点head_new
            return head_new;
        }

### 总结 ###

**迭代方法**：通过**处理重复过程**（两个链表元素的反转），以每次**处理结果作为下次初始值**，不断的通过**改变状态**直至到达最终状态。

**递归**：**以相似的方法重复**，类似与树结构，从根节点找到叶子节点，然后再从叶子节点**往回处理每一个小问题**（两个链表元素的反转）

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/85dcd610eeba470d9924d62db59274dc.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/ce3346e6abd14e3c9377e66e4fde73d8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/ab9bd2b724b845679192c7de91e860ec.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/67be28a0b86648199391695982a41520.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/3e5c7c77c3394e889c8131995c092ba5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/9620d7b916214f618e2cfb055ad1e1f9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/161cdcbc13a542da91cb6e1fbf778f31.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56CB5Yac5bCP5p6X_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/95c7d1f52308419a879f26019bd26f2f.png