单链表反转 Java 《剑指offer》,Leetcode 206. Reverse Linked List

谁践踏了优雅 2021-09-24 12:54 256阅读 0赞

Reverse a singly linked list.

**Example:**

Input: 1->2->3->4->5->NULL
    Output: 5->4->3->2->1->NULL

**Follow up:**

A linked list can be reversed either iteratively or recursively. Could you implement both?

package com.offer;
    
    /**
     * @Author you guess
     * @Date 2020/12/5 09:50
     * @Version 1.0
     * @Desc
     */
    
    
    class ListNode {
        int val;
        ListNode next;
    
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    
    
    public class Leetcode_206_ReverseLinkedList {
    
     /*   static class ListNode {
            int val;
            ListNode next;
    
            ListNode(int val, ListNode next) {
                this.val = val;
                this.next = next;
            }
        }*/
    
    
        /**
         * Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.
         * Memory Usage: 38.9 MB, less than 46.11% of Java online submissions for Reverse Linked List.
         * <p>
         * pre = cur.next;
         * cur.next = pre;
         * 以上2行是有区别的！！！！！
         *
         * @param head
         * @return
         */
        public ListNode reverseList(ListNode head) {
    
            if (head == null)
                return null;
    
            ListNode pre = head;
            ListNode cur = pre.next;
            ListNode post = null;
    
            //此时pre是头指针，需要把next指针断掉，不然后面1<->2互相next会形成环，造成死循环；
            //并且不能在while中写本行代码，不然pre往前的指向就断了！
            pre.next = null;
    
            while (cur != null) {
                post = cur.next;//提前把下一个节点取到
                cur.next = pre; //pre指针不变，变化的是cur.next，此时是要修改cur.next，所以不能写成pre=cur.next;
                pre = cur; //cur指针不变，变化的是pre指针。pre,cur,post依次向前
                cur = post;
            }
            return pre;
        }
    
        public void printListNode(ListNode head) {
            while (head != null) {
                System.out.println(head.val);
                head = head.next;
            }
        }
    
        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);
    
            Leetcode_206_ReverseLinkedList main = new Leetcode_206_ReverseLinkedList();
            main.printListNode(main.reverseList(node1));
    //        输出：
    //        5
    //        4
    //        3
    //        2
    //        1
        }
    
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70][]

第1步：pre,cur,next=1,2,3：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70 1][]

第2步：pre,cur,next=2,3,4：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70 2][]

第3步：pre,cur,next=3,4,5：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70 5][]

第4步：pre,cur,next=4,5,null：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70 6][]

第5步：pre,cur,next=5,null,null：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70 7][]

=======================================================

> 一道经典的面试题——链表反转。接下来就来讲解链表反转的解法。

## 链表反转图示 ##

![format_png][]

## 解法说明 ##

1.  链表反转的本质其实就是把每一个节点原本指向下一个节点的next的指针，反转过来指向它的前置节点。

![format_png 1][]

1.  进行链表反转的时候，需要同时知道三个节点才能进行反转。

![format_png 2][]

## 解法步骤 ##

1、以p2节点为根，把p2节点原本指向p3的next指针反转，指向p1

![format_png 3][]

2、三个临时节点引用**p1，p2，p3分别向后移动一位**

![format_png 4][]

3、重复”1”的工作，以p2节点为根，把p2节点原本指向p3的next指针反转，指向p1

![format_png 5][]

4、重复”2”的工作，三个临时节点引用p1，p2，p3分别向后移动一位

![format_png 6][]

5、继续重复以上的工作，一直到p2为空为止

![format_png 7][]

6、最后，把head节点的next指向空，成为反转链表的尾节点。并把p1赋值给head，让p1所在节点成为反转链表的头节点

![format_png 8][]

**听完上面的讲解，估计有点懵逼，来看看代码的实现，再结合上面的图示步骤，相信你就会理解链表反转了**

## 代码实现 ##

public class ListNode{
        int val;
        ListNode next = null;
        
        ListNode(int val){
            this.val = val;
        }
    }
    
    public class Solution{
        public ListNode ReverseList(ListNode head){//返回头指针即可
            if(head == null || head.next == null){
                return head;
            }
            
            ListNode p1 = head;
            ListNode p2 = head.next;
            ListNode p3 = null;
    
            while(p2 != null){//到最后一个节点时，p1指向最后一个节点，p2/p3均指向null
                p3 = p2.next;
                p2.next = p1;
                p1 = p2;
                p2 = p3;
            }
            head.next = null;
            head = p1;
            return head;
        }
    }

参考

[https://zhuanlan.zhihu.com/p/102908327?utm\_source=wechat\_session&utm\_medium=social&utm\_oi=601913170005331968][https_zhuanlan.zhihu.com_p_102908327_utm_source_wechat_session_utm_medium_social_utm_oi_601913170005331968]

[https://blog.csdn.net/geekmanong/article/details/51097196][https_blog.csdn.net_geekmanong_article_details_51097196]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70]: /images/20210923/844972c29f5148d98289daca1d8e8a34.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70 1]: /images/20210923/e8a791236f404d7a808fb3f55b8211b5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70 2]: /images/20210923/5c58876fd5ce465ab3d82fd75a1f67e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70 3]: /images/20210923/fd2234278eab4aa4acfcdbc78805bdca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70 4]: /images/20210923/37ef6651c5114eb2856edfe7b2a0ad40.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70 5]: /images/20210923/221b1c45910e44e2a3a2bcc8f62a5db9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70 6]: /images/20210923/3aba38f31c8045348c6bad378bde330b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMDIxODQ_size_16_color_FFFFFF_t_70 7]: /images/20210923/6db6b5e1870b42a4997c10000f11b38b.png
[format_png]: /images/20210923/6be285c412fa4b2480e919ec04f25208.png
[format_png 1]: /images/20210923/a3f922c348374265bb8f7eba010e513c.png
[format_png 2]: /images/20210923/691add92224f4b2f9bb12306a26cae1b.png
[format_png 3]: /images/20210923/8b44776da311479bb89601cea8d645ff.png
[format_png 4]: /images/20210923/1ad3432ee1964d26b3a2099cdc09b449.png
[format_png 5]: /images/20210923/2cd12565244d4d4ab7116f2b281940c5.png
[format_png 6]: /images/20210923/8aa14d1fb6234ec99796d44950f46dfa.png
[format_png 7]: /images/20210923/e492bebfaa504ae5a4d298190f632b68.png
[format_png 8]: /images/20210923/9e9a38a4074a4529806e51696fc4dbd3.png
[https_zhuanlan.zhihu.com_p_102908327_utm_source_wechat_session_utm_medium_social_utm_oi_601913170005331968]: https://zhuanlan.zhihu.com/p/102908327?utm_source=wechat_session&utm_medium=social&utm_oi=601913170005331968
[https_blog.csdn.net_geekmanong_article_details_51097196]: https://blog.csdn.net/geekmanong/article/details/51097196

发表评论取消回复

表情：

评论列表（有 0 条评论，256人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode:206. Reverse Linked List反转链表(C语言)

题目描述：反转一个单链表。示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 解答： / D

浅浅的花香味﹌/ 2023年06月24日 09:27/ 0 赞/ 110 阅读

相关力扣Leetcode 206 | 反转链表（Reverse Linked List）

> 作者：ame-9 > 链接：https://leetcode-cn.com/problems/reverse-linked-list/solution/python3d

淡淡的烟草味﹌/ 2022年12月16日 15:27/ 0 赞/ 115 阅读

相关算法: 翻转链表 206. Reverse Linked List

206. Reverse Linked List Given the head of a singly linked list, reverse the list, an

约定不等于承诺〃/ 2022年08月28日 04:49/ 0 赞/ 148 阅读

相关 LeetCode-Reverse Linked List II（反转链表）

题目： Reverse a linked list from position m to n. Do it in-place and in one-pass. For ex

小灰灰/ 2022年08月07日 02:43/ 0 赞/ 3 阅读

相关 206. Reverse Linked List （转置单链表）

Reverse a singly linked list. Hint: A linked list can be reversed either iteratively o

秒速五厘米/ 2022年07月15日 01:22/ 0 赞/ 113 阅读

相关 leetcode 206. Reverse Linked List 反转字符串

Reverse a singly linked list. 反转链表，我这里是采用头插法来实现反转链表。代码如下： /class ListNode {

布满荆棘的人生/ 2022年06月08日 09:14/ 0 赞/ 120 阅读

相关 [Leetcode][python][Java]Reverse Linked List/Reverse Linked List II/反转链表/反转链表 II

Reverse Linked List 题目大意翻转链表解题思路必看： http://blog.csdn.net/autumn20080101/a

水深无声/ 2022年06月06日 04:54/ 0 赞/ 207 阅读

相关 LeetCode 206.Reverse Linked List (反转链表)

题目描述：反转一个单链表。示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL AC C++ So

谁践踏了优雅/ 2022年04月15日 01:15/ 0 赞/ 139 阅读

相关单链表反转 Java 《剑指offer》,Leetcode 206. Reverse Linked List

Reverse a singly linked list. Example: Input: 1->2->3->4->5->NULL Output: 5->4

谁践踏了优雅/ 2021年09月24日 12:54/ 0 赞/ 257 阅读

相关 LeetCode : 206. Reverse Linked List 反转链表

试题 Reverse a singly linked list. Example: Input: 1->2->3->4->5->NULL Output: 5->4-

痛定思痛。/ 2021年06月24日 16:11/ 0 赞/ 373 阅读