Java 反转单链表

Love The Way You Lie 2023-10-09 13:45 42阅读 0赞

#### 文章目录 ####

*  反转单链表
 *   *  1.描述
     *  2.方法一
     *   *  思路分析
         *  图示
         *  代码
     *  3.方法二
     *   *  思路分析
         *  图示
         *  代码
     *  4.方法三
     *   *  思路分析
         *  图示
         *  代码

## 反转单链表 ##

### 1.描述 ###

给你单链表的头指针head ，请你反转链表，并返回反转后的链表。  
如下：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16]

### 2.方法一 ###

#### 思路分析 ####

1）创建一个新的头指针newHead。  
2）创建一个结点p遍历反转前的链表，每遍历一个结点，把newHead指向当前结点。同时创建一个结点cur，用来保存p的下一个结点，以此来保证p遍历整个反转前的链表。  
3）最后原来头指针head，指向新的链表。

#### 图示 ####

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

#### 代码 ####

/**
     * Definition for singly-linked list.
     * public class Node {
     *     int val;
     *     Node next;
     *     Node() {}
     *     Node(int val) { this.val = val; }
     *     Node(int val, Node next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public void reverse(Node head) {
        
            //链表为空，或链表长度为1
            if (head == null || head.next == null) {
        
                return;
            }
    
            Node p = head;
            Node newHead;
            Node cur;
    
            cur = p.next;
            newHead = p;
            p.next = null;//新链表的尾结点，next域置为null
            while (cur != null) {
        
                p = cur;
                cur = p.next;
                p.next = newHead;
                newHead = p;
            }
            head = newHead;
        }
    }

### 3.方法二 ###

#### 思路分析 ####

把一个单链表逆转，我们直接把每个结点的next域直接指向前一个结点不就可以了吗（第一个结点的next域置为空），最后把head指向反转链表前的最后一个结点。如下：  
![在这里插入图片描述][b7fb88732870485fbe3879310de29cc7.gif]  
1）设置一个结点p指向head。  
2）设置一个结点q指向p的下一个结点。  
3）设置一个s指向q的下一个结点。  
4）头结点的next域置为null。  
5）q的next域指向p。  
6）因为头结点的next域已经置为null,所以把q赋值给p，来移动到下一个结点。  
7）q借助s移动到下一个结点。  
8）s移动到下一个结点。  
9）循环操作2~8直到q为null。

#### 图示 ####

![在这里插入图片描述][6fd55ef88e6349d58d7a9e589c3ed2d0.gif]

#### 代码 ####

/**
     * Definition for singly-linked list.
     * public class Node {
     *     int val;
     *     Node next;
     *     Node() {}
     *     Node(int val) { this.val = val; }
     *     Node(int val, Node next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public void reverse(Node head) {
        
            //链表为空或链表长度为1
            if (head == null || head.next == null) {
        
                return;
            }
    
            Node<E> p = head,q = p.next,s = q.next;
            head.next = null;//新尾巴
    
            while (q != null) {
        
                q.next = p;
                p = q;
                q = s;
                if (s != null) {
        
                    s = s.next;
                }
            }
            head = p;//指向新头
        }
    }

### 4.方法三 ###

#### 思路分析 ####

1）创建一个新的头指针pre，初始化为null。  
2）创建一个结点cur指向当前结点。  
3）当前结点的next域指向pre。  
4）pre借助cur指向下一个结点。  
5）cur指向原来链表的下一个结点（因为第三步中cur指向的结点的next域已经更新，需要一个Cur\_next结点来完成移动，cur完成移动后，Cur\_next移向下一个结点）。  
6）循环2~5操作，直到cur为null。  
7）返回pre。

#### 图示 ####

![在这里插入图片描述][186070971ea6465f8e2b31f588a6cceb.gif]

#### 代码 ####

/**
     * Definition for singly-linked list.
     * public class Node {
     *     int val;
     *     Node next;
     *     Node() {}
     *     Node(int val) { this.val = val; }
     *     Node(int val, Node next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
         public Node ReverseList(Node head) {
        
            //链表为空或链表长度为1
            if(head == null || head.next == null) {
        
                return null;
            }
             
            Node pre = null;//pre指针：用来指向反转后的节点，初始化为null 
            Node cur = head; //当前节点指针
            
            //循环迭代
            while(cur != null) {
        
                //Cur_next 节点，永远指向当前节点cur的下一个节点
                Node Cur_next = cur.next;
                //反转的关键：当前的节点指向其前一个节点
                cur.next = pre;
                 //更新pre
                pre = cur;
                //更新当前节点指针
                cur = Cur_next;
            }
            return pre;
        }
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/434d129951534b34940378ee20dba116.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAV1lTQ09ERVI=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/f257859df1c74196bfc660d672f5ea02.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAV1lTQ09ERVI=,size_20,color_FFFFFF,t_70,g_se,x_16
[b7fb88732870485fbe3879310de29cc7.gif]: https://img-blog.csdnimg.cn/b7fb88732870485fbe3879310de29cc7.gif
[6fd55ef88e6349d58d7a9e589c3ed2d0.gif]: https://img-blog.csdnimg.cn/6fd55ef88e6349d58d7a9e589c3ed2d0.gif
[186070971ea6465f8e2b31f588a6cceb.gif]: https://img-blog.csdnimg.cn/186070971ea6465f8e2b31f588a6cceb.gif