題目要求
輸入一個(gè)鏈表的頭結(jié)點(diǎn)绘闷,從尾到頭打印出每一個(gè)節(jié)點(diǎn)橡庞。
題目解析
思路一:
- 注意,其中ListNode 是一個(gè)自定義的鏈表節(jié)點(diǎn)類型簸喂。
- 分析
利用stack先進(jìn)后出的性質(zhì)毙死,將鏈表所有元素壓入棧燎潮,完全壓入后喻鳄,再將元素一一取出,即為倒序确封。
- 代碼段
public static void printListReceverse(ListNode headNode) {
Stack<ListNode> stack = new Stack<ListNode>() ;
while(headNode != null) {
stack.push(headNode);
headNode = headNode.getNext() ;
}
while(!stack.isEmpty()) {
System.out.println(stack.pop().getData());
}
}
思路二:
- 分析
利用遞歸完成倒序輸出
終止條件為當(dāng)前節(jié)點(diǎn)沒(méi)有下一個(gè)節(jié)點(diǎn)除呵。即headNode.getNext() == null
利用遞歸達(dá)到最后一個(gè)節(jié)點(diǎn)處,然后倒序輸出爪喘。
- 代碼段
public static void printListReceverse1(ListNode headNode) {
if(headNode != null) {
if(headNode.getNext() != null) {
printListReceverse1(headNode.getNext()) ;
}
}
System.out.println(headNode.getData());
}
測(cè)試代碼
public static void main(String[] args) {
ListNode node1 = new ListNode() ;
ListNode node2 = new ListNode() ;
ListNode node3 = new ListNode() ;
node1.setData(1);
node2.setData(2);
node3.setData(3);
node1.setNext(node2);
node2.setNext(node3);
printListReceverse(node1) ;
System.out.println("----------------------------------------------------");
printListReceverse1(node1) ;
}
運(yùn)行結(jié)果
3
2
1
3
2
1