Java面试题：链表-反转链表

问题描述

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

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

示例

输入：{1,2,3}

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

原题地址：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;
    }
}
1
2
3
4
5
6
7
8
9
10
11

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
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

输出结果

1 2 3 
3 2 1
1
2