19. 单链表反转

时间限制：10.000S 空间限制：128MB

题目描述

根据一个整数序列构造一个单链表，然后将其反转。

例如：原单链表为 2 3 4 5 ，反转之后为5 4 3 2

输入描述

输入包括多组测试数据，每组测试数据占一行，第一个为大于等于0的整数n，表示该单链表的长度，后面跟着n个整数，表示链表的每一个元素。整数之间用空格隔开

输出描述

针对每组测试数据，输出包括两行，分别是反转前和反转后的链表元素，用空格隔开

如果链表为空，则只输出一行，list is empty

输入示例

5 1 2 3 4 5

0

输出示例

1 2 3 4 5

5 4 3 2 1

list is empty

提示信息

本题用数组，也是可有过的，输入一遍数组，然后倒叙输出。不过建议大家用本题来链表操作

解法一(模拟)

思路分析:

1. 自建链表进行操作
2. 按照题目意思进行列表反转, 可以循环链表,将前面的节点依次插入到原本的最后一个节点之后实现翻转

实现代码如下:

public class k_19_SinglyLinkedListReversal {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n;  // 列表长度
        while (in.hasNext()) {
            n = in.nextInt();
            LinkedList first = new LinkedList();
            LinkedList end = first;
//            first.next = end;
            while (n-- > 0) {
                int val = in.nextInt();
                end.next = new LinkedList(val);
                end = end.next;
            }
            if (first.next != null) {
                // 输出正序
                for (LinkedList p = first.next; p != end.next; p = p.next) {
                    System.out.print(p.val + " ");
                }
                System.out.println();
                // 反转
                LinkedList q = first.next;
                while (q != end) {
                    // 取出节点
                    LinkedList temp = q;
                    q = q.next;
                    temp.next = null;
                    // 插入end之后
                    temp.next = end.next;
                    end.next = temp;
                }
                // 输出反转
                for (LinkedList i = end; i != null; i = i.next) {
                    System.out.print(i.val + " ");
                }
                System.out.println();
            } else {
                System.out.println("list is empty");
            }
        }
    }
    private static class LinkedList {
        int val;
        LinkedList next;
        public LinkedList() {
            this.next = null;
        }
        public LinkedList(int val) {
            this.val = val;
            this.next = null;
        }
        public LinkedList(int val, LinkedList next) {
            this.val = val;
            this.next = next;
        }
    }
}

运行结果如下:

运行时间： 2427ms 消耗内存： 59716kb

复杂度分析:

• 时间复杂度: $O(n)$
• 空间复杂度: $O(n)$