Java面试题:链表-反转链表
  ndh0xMjNGcR6 2023年11月05日 31 0

问题描述

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

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

示例

输入:{1,2,3}

返回值:{3,2,1}

原题地址:https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca

代码实现

链表节点数据

package com.example.demo;


public class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int val) {
        this.val = val;
    }
}
package com.example.demo;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode ReverseList(ListNode head) {
        // head为当前节点,如果当前节点为空的话,那就什么也不做,直接返回null;
        if (head == null) {
            return null;
        }

        // 当前节点是head,pre为当前节点的前一节点,next为当前节点的下一节点
        ListNode pre = null;
        ListNode next = null;

        // 需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2
        // 即pre让节点可以反转所指方向,但反转之后如果不用next节点保存next1节点的话,此单链表就此断开了
        // 所以需要用到pre和next两个节点
        // 1->2->3->4->5
        // 1<-2<-3 4->5
        while (head != null) {
            //做循环,如果当前节点不为空的话,始终执行此循环,此循环的目的就是让当前节点从指向next到指向pre
            //如此就可以做到反转链表的效果
            //先用next保存head的下一个节点的信息,保证单链表不会因为失去head节点的原next节点而就此断裂
            next = head.next;
            //保存完next,就可以让head从指向next变成指向pre了,代码如下
            head.next = pre;
            //head指向pre后,就继续依次反转下一个节点
            //让pre,head,next依次向后移动一个节点,继续下一次的指针反转
            pre = head;
            head = next;
        }
        //如果head为null的时候,pre就为最后一个节点了,但是链表已经反转完毕,pre就是反转后链表的第一个节点
        //直接输出pre就是我们想要得到的反转后的链表
        return pre;
    }

    // 打印链表
    public static void printNodeList(ListNode head) {
        ListNode current = head;

        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        //{1,2,3}
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        printNodeList(listNode1);

        ListNode listNode = new Solution().ReverseList(listNode1);

        printNodeList(listNode);
    }
}

输出结果

1 2 3 
3 2 1
【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2023年11月08日 0

暂无评论

推荐阅读
  2Vtxr3XfwhHq   2024年05月17日   39   0   0 Java
  8s1LUHPryisj   2024年05月17日   36   0   0 Java
  aRSRdgycpgWt   2024年05月17日   38   0   0 Java
ndh0xMjNGcR6