NC78 反转链表

题目链接：https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca

题目描述

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

数据范围： 0≤n≤1000

要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

示例 1：

输入：{1,2,3}
返回值：{3,2,1}

示例 2：

输入：{}
返回值：{}
说明：空链表则输出空

解题代码

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        //记录当前结点
        ListNode nowNode = head;
        //记录当前结点的上一个结点
        ListNode preNode = null;
        //从头结点开始遍历链表
        while (nowNode != null) {
            //记录当前结点的下一个结点，如果不保存断开连接后就找不到了
            ListNode nextNode = nowNode.next;
            //将当前结点与前一个结点连接
            nowNode.next = preNode;
            //让当前结点成为前一个结点
            preNode = nowNode;
            //让后一个结点成为前一个结点
            nowNode = nextNode;
        }
        //返回的这个是反转后的头结点，反转后它从上一个结点变成了后一个结点，最终变成了开头
        return preNode;
    }
}

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请标明出处。
最后编辑时间为: 2022/07/07 11:11:56