devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode 206. 反转链表 java版 多种简单方式，总有一款适合你！超级简单易懂的反转链表 java_反转链表 java leetcode

作者：你好赵伟 | 2024-07-26 14:53:31

赞

踩

反转链表 java leetcode

1. 官方链接

. - 力扣（LeetCode）

2. 题目：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

 3. 方案

     解决方式1：

                      迭代链表，每次new一个节点，并将老节点放入newNode 的next

                      我认为这种很容易理解，当然缺点就是每次new一个对象

  1. package com.nami.algorithm.study.chain2;
  2.  
  3. /**
  4.  * 描述: 反转链表
  5.  * <p>
  6.  * 构造一个新链表，从旧链表依次拿到每个节点，创建新节点添加至新链表头部，完成后新链表即是倒序的
  7.  *
  8.  * @Author: lbc
  9.  * @Date: 2024-04-16 18:39
  10.  * @email: 594599620@qq.com
  11.  * @Description: keep coding
  12.  */
  13. public class ChainTest {
  14.  
  15.     /**
  16.      * 每次新增一个node 将 next 指向上一个节点。
  17.      *
  18.      * @param node
  19.      * @return
  20.      */
  21.     public static ListNode reverse(ListNode node) {
  22.         ListNode head = null;
  23.         ListNode cur = node;
  24.         while (cur != null) {
  25.             // new一个新节点，将老的放到新节点next
  26.             ListNode o1 = new ListNode(cur.value, head);
  27.             head = o1;
  28.             cur = cur.next;
  29.         }
  30.         return head;
  31.     }
  32.  
  33.     public static void main(String[] args) {
  34.         ListNode n5 = new ListNode(5, null);
  35.         ListNode n4 = new ListNode(4, n5);
  36.         ListNode n3 = new ListNode(3, n4);
  37.         ListNode n2 = new ListNode(2, n3);
  38.         ListNode n1 = new ListNode(1, n2);
  39.  
  40.         ListNode reverse = reverse(n1);
  41.  
  42.         while (reverse != null) {
  43.             System.out.println(reverse.value);
  44.             reverse = reverse.next;
  45.         }
  46.  
  47.     }
  48.  
  49.     static class ListNode {
  50.  
  51.         protected int value;
  52.  
  53.         protected ListNode next;
  54.  
  55.         public ListNode(int value, ListNode next) {
  56.             this.value = value;
  57.             this.next = next;
  58.         }
  59.  
  60.     }
  61.  
  62. }

  方法2:

               使用自定义容器类，链表放入容器类。使用容器方法removeFirst, addFirst 将老链表数据转换新容器对象内

  1. package com.nami.algorithm.study.chain3;
  2.  
  3. /**
  4.  * 描述:
  5.  *      单项链表反转
  6.  *
  7.  * @Author: lbc
  8.  * @Date: 2024-04-16 20:49
  9.  * @email: 594599620@qq.com
  10.  * @Description: keep coding
  11.  */
  12. public class ChainTest {
  13.  
  14.     /**
  15.      * 构造一个新链表，从旧链表头部移除节点，添加到新链表头部，完成后新链表是倒序的，
  16.      * 使用两个自定义容器，容器内有移除与新增方法
  17.      *
  18.      * @param node
  19.      * @return
  20.      */
  21.     public static ListNode reverse(ListNode node) {
  22.         ChainList result = new ChainList(null);
  23.         ChainList list = new ChainList(node);
  24.         while (true) {
  25.             ListNode listNode = list.removeFirst();
  26.             if (listNode == null) {
  27.                 break;
  28.             }
  29.             result.addFirst(listNode);
  30.         }
  31.  
  32.         return result.head;
  33.     }
  34.  
  35.  
  36.     public static void main(String[] args) {
  37.  
  38.         ListNode n5 = new ListNode(5, null);
  39.         ListNode n4 = new ListNode(4, n5);
  40.         ListNode n3 = new ListNode(3, n4);
  41.         ListNode n2 = new ListNode(2, n3);
  42.         ListNode n1 = new ListNode(1, n2);
  43.  
  44.         ListNode node = reverse(n1);
  45.  
  46.         while (node != null) {
  47.             System.out.println(node.value);
  48.             node = node.next;
  49.         }
  50.     }
  51.  
  52.  
  53.     /**
  54.      * 容器类
  55.      * 核心 removeFirst
  56.      * addFirst
  57.      */
  58.     static class ChainList {
  59.         private ListNode head;
  60.  
  61.         public ChainList(ListNode head) {
  62.             this.head = head;
  63.         }
  64.  
  65.         public void addFirst(ListNode node) {
  66.             node.next = head;
  67.             head = node;
  68.         }
  69.  
  70.         public ListNode removeFirst() {
  71.             if (head == null) {
  72.                 return null;
  73.             }
  74.             ListNode first = head;
  75.             head = head.next;
  76.             return first;
  77.         }
  78.  
  79.     }
  80.  
  81.     static class ListNode {
  82.  
  83.         protected int value;
  84.  
  85.         protected ListNode next;
  86.  
  87.         public ListNode(int value, ListNode next) {
  88.             this.value = value;
  89.             this.next = next;
  90.         }
  91.  
  92.     }
  93.  
  94.  
  95. }

方法3：

        图解：看一遍就理解，图解单链表反转 - 掘金

        头插法

  1. package com.nami.algorithm.study.chain;
  2.  
  3. /**
  4.  * 描述: 反转链表
  5.  * 头插法
  6.  *
  7.  * @Author: lbc
  8.  * @Date: 2024-04-17 9:38
  9.  * @email: 594599620@qq.com
  10.  * @Description: keep coding
  11.  */
  12. public class ChainTest {
  13.  
  14.     public static ListNode reverseNode(ListNode head) {
  15.         ListNode prev = null;
  16.  
  17.         ListNode cur = head;
  18.  
  19.         while (cur != null) {
  20.             // 这样好理解 ==! 但是感觉跟方法一 差不多
  21.             ListNode node = new ListNode(cur.value, cur.next);
  22.             node.next = prev;
  23.             prev = node;
  24.  
  25.             // 循环
  26.             cur = cur.next;
  27.         }
  28.  
  29.         return prev;
  30.     }
  31.  
  32.  
  33.     public static ListNode reverseNode2(ListNode head) {
  34.         // 最终节点
  35.         ListNode prev = null;
  36.         // 当前节点
  37.         ListNode cur = head;
  38.  
  39.         while (cur != null) {
  40.             // 想想上面的reverseNode（） 方法不难，主要是解决一个 ”引用问题“
  41.             // 相当于将cur = cur.next; 放在第一行。拿出next节点。防止cur.next 这个循环条件被污染
  42.             // 建议比较方法1 比较着看
  43.             ListNode next = cur.next;
  44.  
  45.             cur.next = prev;
  46.  
  47.             prev = cur;
  48.  
  49.             // 循环
  50.             cur = next;
  51.         }
  52.  
  53.         return prev;
  54.     }
  55.  
  56.  
  57.     public static void main(String[] args) {
  58.  
  59.         ListNode n1 = new ListNode(1);
  60.         ListNode n2 = new ListNode(2);
  61.         ListNode n3 = new ListNode(3);
  62.         ListNode n4 = new ListNode(4);
  63.         ListNode n5 = new ListNode(5);
  64.  
  65.         n1.next = n2;
  66.         n2.next = n3;
  67.         n3.next = n4;
  68.         n4.next = n5;
  69.  
  70.         ListNode listNode = reverseNode2(n1);
  71.  
  72.         while (listNode != null) {
  73.             System.out.println(listNode.value);
  74.             listNode = listNode.next;
  75.         }
  76.  
  77.     }
  78.  
  79.  
  80.     static class ListNode {
  81.  
  82.         protected int value;
  83.  
  84.         protected ListNode next;
  85.  
  86.         public ListNode(int value) {
  87.             this.value = value;
  88.         }
  89.  
  90.         public ListNode(int value, ListNode next) {
  91.             this.value = value;
  92.             this.next = next;
  93.         }
  94.  
  95.     }
  96.  
  97. }

方法4：

          还是使用容器

           采用栈，先进后出思路解决

  1. package com.nami.algorithm.study.chain;
  2.  
  3. import java.util.Stack;
  4.  
  5. /**
  6.  * 描述: 反转链表
  7.  * 头插法
  8.  *
  9.  * @Author: lbc
  10.  * @Date: 2024-04-17 9:38
  11.  * @email: 594599620@qq.com
  12.  * @Description: keep coding
  13.  */
  14. public class ChainTest2 {
  15.  
  16.     public static ListNode reverseNode(ListNode head) {
  17.         Stack<ListNode> stack = new Stack<>();
  18.         while (head != null) {
  19.             stack.push(head);
  20.             head = head.next;
  21.         }
  22.         if (stack.isEmpty()) {
  23.             return null;
  24.         }
  25.         ListNode newHead = stack.pop();
  26.         head = newHead;
  27.         while (!stack.isEmpty()) {
  28.             head.next = stack.pop();
  29.             head = head.next;
  30.         }
  31.         head.next = null;
  32.         return newHead;
  33.     }
  34.  
  35.  
  36.     public static void main(String[] args) {
  37.  
  38.         ListNode n1 = new ListNode(1);
  39.         ListNode n2 = new ListNode(2);
  40.         ListNode n3 = new ListNode(3);
  41.         ListNode n4 = new ListNode(4);
  42.         ListNode n5 = new ListNode(5);
  43.  
  44.         n1.next = n2;
  45.         n2.next = n3;
  46.         n3.next = n4;
  47.         n4.next = n5;
  48.  
  49.         ListNode listNode = reverseNode(n1);
  50.  
  51.         while (listNode != null) {
  52.             System.out.println(listNode.value);
  53.             listNode = listNode.next;
  54.         }
  55.  
  56.     }
  57.  
  58.  
  59.     static class ListNode {
  60.  
  61.         protected int value;
  62.  
  63.         protected ListNode next;
  64.  
  65.         public ListNode(int value) {
  66.             this.value = value;
  67.         }
  68.  
  69.         public ListNode(int value, ListNode next) {
  70.             this.value = value;
  71.             this.next = next;
  72.         }
  73.  
  74.     }
  75.  
  76. }

方法5：

           递归方式                  

  1. package com.nami.algorithm.study.chain;
  2.  
  3. /**
  4.  * 描述: 反转链表
  5.  * 头插法
  6.  *
  7.  * @Author: lbc
  8.  * @Date: 2024-04-17 9:38
  9.  * @email: 594599620@qq.com
  10.  * @Description: keep coding
  11.  */
  12. public class ChainTest3 {
  13.  
  14.     /**
  15.      * 递归  注意层数问题，别 stackOverFlow 喽
  16.      * 堆栈溢出异常
  17.      *
  18.      * @param head
  19.      * @return
  20.      */
  21.     public static ListNode reverseNode(ListNode head) {
  22.         if (head == null || head.next == null) {
  23.             return head;
  24.         }
  25.  
  26.         ListNode last = reverseNode(head.next);
  27.         head.next.next = head;
  28.         head.next = null;
  29.         return last;
  30.     }
  31.  
  32.  
  33.     public static void main(String[] args) {
  34.  
  35.         ListNode n1 = new ListNode(1);
  36.         ListNode n2 = new ListNode(2);
  37.         ListNode n3 = new ListNode(3);
  38.         ListNode n4 = new ListNode(4);
  39.         ListNode n5 = new ListNode(5);
  40.  
  41.         n1.next = n2;
  42.         n2.next = n3;
  43.         n3.next = n4;
  44.         n4.next = n5;
  45.  
  46.         ListNode listNode = reverseNode(n1);
  47.  
  48.         while (listNode != null) {
  49.             System.out.println(listNode.value);
  50.             listNode = listNode.next;
  51.         }
  52.  
  53.     }
  54.  
  55.  
  56.     static class ListNode {
  57.  
  58.         protected int value;
  59.  
  60.         protected ListNode next;
  61.  
  62.         public ListNode(int value) {
  63.             this.value = value;
  64.         }
  65.  
  66.         public ListNode(int value, ListNode next) {
  67.             this.value = value;
  68.             this.next = next;
  69.         }
  70.  
  71.     }
  72.  
  73. }

最后：

          如果觉得困难 建议debug, 跟下。 多看代码，多思考，相信很快就明白了

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号