从尾到头打印链表-爱代码爱编程
从尾到头打印链表,解法一:借助栈
public ArrayList<Integer> printListFromTailToHead(ListNode listNode){
ArrayList<Integer> list=new ArrayList<>();
Stack<ListNode>stack=new Stack<>();
while(head!=null){
stack.push(head);
head=head.next;
}
while(!stack.empty()){
list.add(stack.pop().val);
}
return list;
}
解法二:递归
public ArrayList<Integer> printListReverse2(ListNode headNode){
ArrayList<Integer> list=new ArrayList<>();
if(headNode!=null){
if(headNode.next!=null){
list=printListReverse2(headNode.next);
}
list.add(headNode.val);
}
return list;
}
完整代码如下,其中包含了添加节点的方法add()方法、基本打印节点的方法list(),替换空格的方法replaceSpace()和其他无关方法和本章节没有关系,可以删去。
package www.it.com;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class ReplaceSpace {
public ListNode head=new ListNode(0);
//替换字符串中的空格
public static String replaceSpace(StringBuffer str){
if(str==null)
return null;
StringBuilder sb=new StringBuilder();
for(int i=0;i<str.length();i++){
if(String.valueOf(str.charAt(i)).equals(" ")){
sb.append("20%");
}
else{
sb.append(str.charAt(i));
}
}
return String.valueOf(sb);
}
//从尾到头打印链表,解法一:借助栈
public ArrayList<Integer> printListFromTailToHead(ListNode listNode){
ArrayList<Integer> list=new ArrayList<>();
Stack<ListNode>stack=new Stack<>();
while(head!=null){
stack.push(head);
head=head.next;
}
while(!stack.empty()){
list.add(stack.pop().val);
}
return list;
}
//从尾到头打印链表,解法一:借助栈2
public int[] reversePrint(ListNode head) {
if(head == null){
return new int[0];
}
Stack<Integer> stack = new Stack();
while(head.next!= null){
stack.push(head.val);
head = head.next;
}
stack.push(head.val);//注意这句
//while(head!= null){
// stack.push(head.val);
// head = head.next;
//}
//stack.push(head.val);//注意这句
int[] res = new int[stack.size()];
int i = 0;
while(!stack.isEmpty()){
res[i++] = stack.pop();
}
return res;
}
//解法二:递归
public ArrayList<Integer> printListReverse2(ListNode headNode){
ArrayList<Integer> list=new ArrayList<>();
if(headNode!=null){
if(headNode.next!=null){
list=printListReverse2(headNode.next);
}
list.add(headNode.val);
}
return list;
}
public void add(ListNode listNode){
ListNode temp=head;
while(true){
if(temp.next==null){
break;
}
temp=temp.next;
}
temp.next=listNode;
}
public void list(){
if(head.next==null){
System.out.println("链表为空");
return;
}
ListNode temp=head.next;
while(true){
if(temp==null){
break;
}
//输出节点信息
System.out.println(temp);
temp=temp.next;
}
}
public static void main(String[] args) {
// 1、替换字符串中的空格
// StringBuffer sb=new StringBuffer("We Are Happy");
// String s=replaceSpace(sb);
// System.out.println(s);
// 2、从尾到头打印链表,解法一:借助
ListNode l1=new ListNode(1);
ListNode l2=new ListNode(2);
ListNode l3=new ListNode(3);
ListNode l4=new ListNode(4);
ListNode l5=new ListNode(5);
ListNode l6=new ListNode(6);
ListNode l7=new ListNode(7);
ListNode l8=new ListNode(8);
ReplaceSpace rs=new ReplaceSpace();
rs.add(l1);
rs.add(l2);
rs.add(l3);
rs.add(l4);
rs.add(l5);
rs.add(l6);
rs.add(l7);
rs.add(l8);
rs.list();
System.out.println("---------------------------");
ArrayList<Integer> list=rs.printListReverse2(l1);
//使用栈完成倒置时,i到list.size()结束,不打印头结点。
for(int i = 0;i < list.size(); i ++){
System.out.println(list.get(i));
}
// int[] s=rs.reversePrint(l1);
// for(int i=0;i<s.length;i++){
// System.out.println(s[i]);
// }
}
}
class ListNode{
int val;
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
ListNode next;
public ListNode(int val){
this.val=val;
}
@Override
public String toString() {
return "ListNode [val=" + val + "]";
}
}