关于数据结构:剑指offer3-从尾到头打印单链表值JavaPython

从尾到头打印单链表值

1. 题目形容

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

2. 示例

无

3. 解题思路

此题比较简单

第一种办法：应用数组。先从头到尾读取链表数据，保留到一个数组 a 中。因为要获取从尾到头数据，新开一个数组 b，从数组 a 尾部到头部开始读取，保留到数组 b 中。

第二种办法：应用栈。先从头到尾读取链表数据，保留到一个栈 a 中。利用栈先进后出的性质，pop 到数组 a 中。

4. Java 实现

办法一：应用数组

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {ArrayList<Integer> res = new ArrayList();
        if (listNode == null){return res;}
        
        while(listNode != null){res.add(listNode.val);
            listNode = listNode.next;
            
        }
        ArrayList<Integer> ress = new ArrayList();
        for(int i = res.size()-1; i >= 0; i--){ress.add(res.get(i));
        }
        return ress;
        
    }
}

办法二：应用栈

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;
 
public class Solution {public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        // 应用栈构造实现
        ArrayList<Integer> res = new ArrayList();
        if (listNode == null){return res;}
        Stack<Integer> stack = new Stack();
        while (listNode != null){stack.push(listNode.val);
            listNode = listNode.next;
        }
        
        while (!stack.isEmpty()){res.add(stack.pop());
            
        }
        return res;
        
        
    }
}

5. Python 实现

第一种办法应用栈

第二种间接数组头插法，代码简洁，然而复杂度较高

# 从尾到头顺次打印单链表的值# 从尾到头顺次打印单链表的值
class ListNode:
    def __init__(self, x=None):
        self.val = x
        self.next = None
 
class Solution:
    def printListFromTailToHead(self, listNode):
        if not listNode: #如果头部结点为空
            return 
        stack = []
        while listNode:
            stack.append(listNode.val)
            listNode = listNode.next 
        while stack:
            print(stack.pop())
#         return sorted(stack, reverse=True)   
 
    def printListFromTailToHead2(self, listNode):
        if not listNode:
            return 
        li = []
        while listNode:
            li.insert(0, listNode.val)
            listNode = listNode.next 
        return li 
 
node1 = ListNode(10)
node2 = ListNode(11)
node3 = ListNode(13)
node1.next = node2
node2.next = node3
 
singleNode = ListNode(12)
 
test = ListNode()
 
S = Solution()
print(S.printListFromTailToHead2(node1))
print(S.printListFromTailToHead2(test))
print(S.printListFromTailToHead2(singleNode))   

如果您感觉本文有用，请点个“在看”