个人中心
gpt4 book ai didi

java实现链表反转

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 37 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章java实现链表反转由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

本文为大家分享了java实现链表反转的具体代码，供大家参考，具体内容如下 。

算法题：实现链表的反转 。

提供了2种方法，迭代法、递归法.

（为了方便输出可视化，在自定义的ListNode中重写了toString方法。） 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
  * Created By --- on 2021/8/12
  * 以下代码可以直接粘贴进编译器输出
  */
public class ReverseList {
 
   public static void main(String[] args) {
     ListNode head = new ListNode( 3 , new ListNode( 5 , new ListNode( 8 , new ListNode( 9 ))));
     System.out.println( "初始链表：" + head);
 
     ListNode newList = reverseList(head);
     System.out.println( "使用迭代法反转链表：" + newList);
 
     ListNode newList2 = reverseList2( null , newList);
     System.out.println( "使用递归法反转链表：" + newList2);
   }
 
   /**
    * 迭代法
    */
   public static ListNode reverseList(ListNode head) {
     ListNode pre = null ;
     ListNode cur = head;
     ListNode tmp;
     while (cur != null ) {
       tmp = cur.next;
       cur.next = pre;
       pre = cur;
       cur = tmp;
     }
     return pre;
   }
 
   /**
    * 递归法
    */
   public static ListNode reverseList2(ListNode pre, ListNode cur) {
     if (cur == null ) {
       return pre;
     }
 
     ListNode tmp = cur.next;
     cur.next = pre;
     pre = cur;
     cur = tmp;
     return reverseList2(pre, cur);
   }
 
 
}
 
 
/**
  * singly-linked list
  */
class ListNode {
 
   int val;
   ListNode next;
 
   ListNode() {
   }
 
   ListNode( int val) {
     this .val = val;
   }
 
   ListNode( int val, ListNode next) {
     this .val = val;
     this .next = next;
   }
 
   @Override
   public String toString() {
     StringBuilder sb = new StringBuilder(String.valueOf(val));
     ListNode next = this .next;
     while (next != null ) {
       sb.append(next.val);
       next = next.next;
     }
     return sb.toString();
   }
}

输出结果:

java实现链表反转

  。

再为大家分享一段java实现链表反转的三种方式 。

分别通过栈、递归、指针的方式实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
import java.util.Stack;
 
public class ReverseLinkedList {
 
     public static void main(String[] args) {
         ReverseLinkedList reverseLinkedList = new ReverseLinkedList();
         reverseLinkedList.test();
     }
 
     public void test() {
         Node node1 = new Node( 1 );
         Node node2 = new Node( 2 );
         Node node3 = new Node( 3 );
         node1.setNext(node2);
         node2.setNext(node3);
         //方法需要替换
         node1 = reverseByPointer(node1);
         while (node1 != null ) {
             System.out.println(node1.val);
             node1 = node1.getNext();
         }
     }
 
     //栈实现
     private Node reverseByStack(Node head) {
         if (head == null || head.getNext() == null ) {
             return head;
         }
         Stack<Node> stack = new Stack<>();
         while (head != null ) {
             stack.push(head);
             head = head.getNext();
         }
         head = stack.pop();
         Node tmp = head;
         while (!stack.empty()) {
             Node node = stack.pop();
             node.setNext( null );
             tmp.setNext(node);
             tmp = node;
         }
         return head;
     }
 
     //递归实现
     private Node reverseByRecursion(Node head) {
         if (head == null || head.getNext() == null ) {
             return head;
         }
         //递归获取当前节点的后一个节点
         Node tmp = reverseByRecursion(head.getNext());
         Node node = head.getNext();
         head.setNext( null );
         node.setNext(head);
         return tmp;
     }
 
     //指针实现
     private Node reverseByPointer(Node head) {
         if (head == null || head.getNext() == null ) {
             return head;
         }
         //pre指针指向前一个节点，初始第一个节点的前节点为空
         Node pre = null ;
         //tmp指针指向当前节点
         Node tmp = null ;
         while (head != null ) {
             //tmp指针指向head头指针节点
             tmp = head;
             //head头指针向后遍历
             head = head.getNext();
             //反转，设置当前节点的下一个节点为前一个节点
             tmp.setNext(pre);
             //pre指针向后移动，指向当前节点
             pre = tmp;
         }
         return tmp;
     }
 
     private class Node {
         private int val;
 
         private Node next;
 
         public Node( int val) {
             this .val = val;
         }
 
         public Node getNext() {
             return next;
         }
 
         public void setNext(Node next) {
             this .next = next;
         }
     }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我.

原文链接：https://blog.csdn.net/kqZhu/article/details/119719751 。

最后此篇关于java实现链表反转的文章就讲到这里了,如果你想了解更多关于java实现链表反转的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

37 4 0
文章推荐： 最简单实用的seo知识
文章推荐： MyBatis使用注解开发和无主配置文件开发的情况
文章推荐： 海量关键词布局与优化策略
文章推荐： 网站优化要根据用户需求
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com