MENU

06从尾到头打印链表

• November 22, 2020 • Read: 8 • ,剑指Offer

原题链接

题目描述

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

示例一

输入:head = [1,3,2]
输出:[2,3,1]

限制:

0 <= 链表长度 <= 10000


首先我想到了单链表的就地逆置,请参考我的文章,里面写得很详细:就地逆置单链表

于是写出了以下代码,其为包含头结点的单链表(头结点没有数据):

/* 记录单链表的长度,以便创建返回数组 */
int length = 0;

public int[] reversePrint(ListNode head) {
    // 先就地逆置单链表
    head = reverseList(head);
    int[] result = new int[length];
    // 遍历链表,存储在数组中
    ListNode p = head;
    for (int i = 0; i < length; i++) {
        result[i] = p.next.val;
        p = p.next;
    }
    return result;
}

/**
 * 就地逆置单链表
 * @param head 头结点(不包含数据)
 * @return 返回就地逆置之后的单链表头结点
 */
private ListNode reverseList(ListNode head) {
    // 如果不含头结点,或者一个数都没有
    if(head == null || head.next == null) return head;
    // 至少有一个数
    ++ length;
    // 只有一个数的情况
    if(head.next.next == null){
        return head;
    }
    // 有多个数的情况
    ListNode p = head.next.next;
    // 第一个数将会变成最后一个数,其指针域要置为空
    head.next.next = null;
    // 根据代码,画图你就懂了
    while (p != null){
        ++ length;
        // 保存后面的链表
        ListNode q = p.next;
        p.next = head.next;
        head.next = p;
        p = q;
    }
    return head;
}

在测试时,发现一个问题:

长度不够,很明显,题目说的单链表,应该是不含头结点的单链表,于是,我在就地逆置的过程中,将单链表添加一个头结点,作为工具,将其逆置

/* 记录单链表的长度,以便创建返回数组 */
int length = 0;

public int[] reversePrint(ListNode head) {
    // 先就地逆置单链表
    head = reverseList(head);
    int[] result = new int[length];
    // 遍历链表,存储在数组中
    ListNode p = head;
    for (int i = 0; i < length; i++) {
        result[i] = p.val;
        p = p.next;
    }
    return result;
}

/**
 * 就地逆置单链表
 * @param head 头结点(不包含数据)
 * @return 返回就地逆置之后的单链表头结点
 */
private ListNode reverseList(ListNode head) {
    if(head == null) return head;
    ++ length;
    // 建立一个不含数据的头结点,把原先链表变成一个带头结点的单链表
    ListNode headPre = new ListNode();
    headPre.next = head;
    // 只有一个数
    if(headPre.next.next == null){
        return head;
    }
    ListNode p = headPre.next.next;
    // 逆置后第一个数将会变成最后一个数,其指针应该指向null
    headPre.next.next = null;
    while (p != null){
        ++ length;
        ListNode q = p.next;
        p.next = headPre.next;
        headPre.next = p;
        p = q;
    }
    return headPre.next;
}

跑起来跑起来:

第三天收工!!




作者:喻航

本文标题:06从尾到头打印链表

本文链接:https://onedawn.cn/chain/93.html

版权声明:如无特别声明,本文即为原创文章,仅代表个人观点,版权归 雾满拦江 所有,未经允许不得转载!
Archives Tip
QR Code for this page
Tipping QR Code