单链表三种反转方法-Java

文章目录

• 前言
• 一、单链表结构
• 一、单链表反转（从前到后遍历）效率高，推荐
• 二、单链表反转（利用栈）
• 三、单链表反转（利用递归）难理解，可以学习学习
• 总结

前言

刷leetcode基础题的时候用到了单链表的反转，记录一下反转方法，并用Java语言实现。

提示：以下是本篇文章正文内容，下面案例可供参考

一、单链表结构

1. 首先要明确 单链表节点的构成，一般来说节点包括两个域：
2. 数据域data,   指针域next.。
3. 数据域用来存储当前节点的数据值，指针域用来存储当前指针指向的内容。

二、单链表反转（从前到后遍历）效率高、推荐

1. 基本思路：
   1. 链表的反转关键就是让指针域进行变更，
   2. 初始状态：结点Null→A→B→C→Null 
   3. 需要调整为：结点Null←A←B←C←Null.
   4. 因为最开始是从A开始，所以需要先定义一个链表类型的节点 prev,用于存储当前节点的前置节点。
   5. 再定义一个链表类型的节点next，用来临时存储当前节点的下一个节点。
   6. 最后return prev结点，因为结点之间有指针链接，所以会输出反转后的链表。
2. 具体实现(Java)：

   public ListNode reverse(ListNode head){
       ListNode prev = null;//定义一个前置结点。
       while(head != null){
           //这里要把next放在这里定义，不提前的原因是需要先满足head!= null的条件。
           ListNode next = head.next;
           head.next = prev;//调整指针域，让结点指向前置结点。
           //为下一次做准备
           prev = head;
           head = next;
       }
       return prev;
   }
   /*单链表的定义 Definition for singly-linked list*/
   public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   }
              

三、单链表反转（利用栈）内存消耗高，不推荐

1. 基本思路：
   1. 链表的反转关键就是让指针域进行变更，
   2. 初始状态：结点Null→A→B→C→Null 
   3. 需要调整为：结点Null←A←B←C←Null.
   4. 那么考虑借助栈后进先出的结构特点，每次读取一个结点入栈，最后统一出栈构建新的单链表。
   5. 得到的单链表即为原始单链表的反转。
2. 具体实现（Java）：

   /*单链表的定义 Definition for singly-linked list*/
   public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   }
   public ListNode reverse(ListNode head){
       Stack<Integer> stack = new Stack<>();
       ListNode node = head;
       ListNode prev = null;
       //单链表结点入栈
       while(node != null){
           stack.push(node.val);
           node = node.next;
       }
       //栈中结点出栈构建新的单链表
       while(stack.pop() != null){
           prev.val = stack.pop();
           prev = prev.next;
       }
       return prev;
   }
              

四、单链表反转（利用递归）也不咋地，不推荐，但是不太好理解，可以学习学习。

1. 基本思路：
   1. 链表的反转关键就是让指针域进行变更，
   2. 初始状态：结点Null→A→B→C→Null 
   3. 需要调整为：结点Null←A←B←C←Null.
   4. 那么我们用递归方法，就是让在调整第一个链表的结点的指针域之前，先反转后续结点。
   5. 层层深入，直至到尾结点为止才开始链表的反转。
   6. 最后给出反转后的单链表。
2. 具体实现（Java）:

   /*单链表的定义 Definition for singly-linked list*/
   public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   }
   //利用递归反转单链表
   public ListNode reverse(ListNode head){
       //判断边界情况
       if(head == null || head.next == null)
           return head;
       
       ListNode temp = head.next;//定义链表结点temp暂存当前节点（也就是第一个结点）的指针域。   
       
       ListNode newHead = reverse(head.next);  //对链表进行递归反转。递归就体现在这里 
       
       //这两步属于善后工作。
       temp.next = head;  //调整结点的指针域指向初始第一个结点。
       head.next = null;  //初始第一个结点指向null.
       
       return newHead;  //输出反转后的单链表。
   }
              

总结

以上，就是总结的内容。推荐使用第一种反转链表，递归法可以多看看，有利于理解递归思想。