算法:从尾到头打印链表

从尾到头打印链表

题目描述

从尾到头打印链表

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

分析

先翻转链表, 然后遍历即可

翻转链表思路:

对于1->2->3->4->5来说, 可以维护两个指针: pre, cur分别表示前一个节点和当前节点;

则有:

(pre)2 -> 1

(cur)3->4->5

然后保存cur.next(4)并修改cur.next的指针指向到pre(2):

(cur)3->(pre)2->1

(temp)4->5

然后修改指针即可: pre = cur; cur = temp;

(pre)3->2->1

(cur)4->5

然后继续…

最后cur即为新的头节点

代码

import java.util.List;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<>();
        ListNode reversed = reverseList(listNode);
        while (reversed != null) {
            res.add(reversed.val);
            reversed = reversed.next;
        }
        return res;
    }

    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            if(temp == null) {
                return cur;
            }
            cur = temp;
        }
        return null;
    }
}