剑指Offer:从尾到头打印链表

题目描述

输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。

解题思路

使用栈

public ArrayList printListFromTailToHead(ListNode listNode) {
    Stack stack = new Stack<>();
    while (listNode != null) {
        stack.add(listNode.val);
        listNode = listNode.next;
    }
    ArrayList ret = new ArrayList<>();
    while (!stack.isEmpty())
        ret.add(stack.pop());
    return ret;
}

使用递归

public ArrayList printListFromTailToHead(ListNode listNode) {
    ArrayList ret = new ArrayList<>();
    if (listNode != null) {
        ret.addAll(printListFromTailToHead(listNode.next));
        ret.add(listNode.val);
    }
    return ret;
}

使用头插法

利用链表头插法为逆序的特点。

头结点和第一个节点的区别:

  • 头结点是在头插法中使用的一个额外节点,这个节点不存储值;
  • 第一个节点就是链表的第一个真正存储值的节点。
public ArrayList printListFromTailToHead(ListNode listNode) {
    // 头插法构建逆序链表
    ListNode head = new ListNode(-1);
    while (listNode != null) {
        ListNode memo = listNode.next;
        listNode.next = head.next;
        head.next = listNode;
        listNode = memo;
    }
    // 构建 ArrayList
    ArrayList ret = new ArrayList<>();
    head = head.next;
    while (head != null) {
        ret.add(head.val);
        head = head.next;
    }
    return ret;
}

使用 Collections.reverse()

public ArrayList printListFromTailToHead(ListNode listNode) {
    ArrayList ret = new ArrayList<>();
    while (listNode != null) {
        ret.add(listNode.val);
        listNode = listNode.next;
    }
    Collections.reverse(ret);
    return ret;
}
本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 剑指Offer:从尾到头打印链表

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多