Java反转链表，简单算法-Toy模板网

这篇具有很好参考价值的文章主要介绍了Java反转链表，简单算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Java 单向链表，指的是一种数据结构，用于存储一系列的元素。每个元素包含两部分：一个存储数据的值和一个指向下一个元素的引用。

单向链表由多个节点组成，每个节点都包含一个数据元素和一个指向下一个节点的引用。
链表的起始节点称为头节点，尾节点的引用为空（null）。
每个节点通过指针（引用）连接在一起，形成链表的结构。
Java反转链表，简单算法,Java-基础,java,链表,算法

一、题目

描述:
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围：
0 ≤ n ≤ 000
要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
Java反转链表，简单算法,Java-基础,java,链表,算法

二、答案

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode ReverseList(ListNode head) {
        if(null == head) return null;
        ListNode newList = null;
        while (head != null) {
            ListNode temp = head.next; //临时存储，并移位
            head.next = newList;//当前节点指向上一个节点
            newList = head;//指针后移更新新链表
            head = temp;//指针后移更新旧链表
        }
        return newList;
    }

}

三、我的解决思路

链表的操作是一个挪指针的过程。这是一个单向链表，next是指向下一个节点的方法。
这个题的基本思路就是：不断获取下一个节点放到末尾。
不看代码，先搞个清楚逻辑：
1.默认链表head：1，2，3
2. head.next：2，3

现在我想要获取1，放到next后边就可以完成第一步了。
解决方案就是给默认链表的next置空就搞定了。新建一个链表newList

3.ListNode newList = null;head.next=newList;

这时候默认链表head变成：1

4.此刻head.next：null

到目前为止就反转了第一步了。
但是发现3没了，那处理方案就是搞个临时链表存着next就可以了，这个需要再最开始就操作，不然		到这块3已经没了。

0.临时链表temp=head.next：2，3

5.将head给到newList就完成第一步了：newList = head，newList --> 1

下面还得继续操作head，但是head中只有1是不行的，所以将临时链表给到head。

6.head=temp，head：2，3

依次往复：

0.temp：3
1.head：2，3
2.head.next：3
3.head.next = newList;head：2，1
4.newList = head;newList：2，1
5.head = temp;head：3

再来一次：
0.temp：空
1.head：3
2.head.next：空
3.head.next = newList;head：3，2，1
4.newList = head;newList：3，2，1
5.head = temp;head：空

while判断head不空，此刻head为空了，跳出循环，反转结束。

return newList;

总结

单链表反转是一个基础的算法问题，通常可以通过迭代或递归两种方法来解决。迭代法的时间复杂度为 O(n)，空间复杂度为 O(1)；递归法的时间复杂度为 O(n)，空间复杂度为 O(n)。在实际应用中，应根据具体情况选择合适的解法。文章来源地址https://www.toymoban.com/news/detail-798734.html

到了这里，关于Java反转链表，简单算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！