Java从尾到头打印链表

x33g5p2x  于2021-03-13 发布在 Java  
字(0.6k)|赞(0)|评价(0)|浏览(299)

从尾到头打印链表

规则
输入:链表head
输出: 字符串,每个元素的值
case:

head为null
只有一个节点
有多个节点

思路

从头到尾打印比较简单,但从尾到头打印就需要进行一些思考了 ,首先要思考能否修改链表,比如讲链表进行逆序再打印,复杂度为O(n)和O(1)。本题目的要求不能修改链表。
思路1:申请空间,构造另外一个链表,使用头插法,复杂度为O(n)和O(n)
思路2:遍历链表,保存到栈中,最后出栈并打印,复杂度为O(n)和O(n)
思路3:有了栈的思路,可以使用递归,复杂度为O(n)和O(n)

代码

// 使用栈
public String reverse(ListNode head) {
		if(head == null) return "";
		Stack<Integer> stack = new Stack<Integer>();
		while(head != null) {
			stack.push(head.val);
			head = head.next;
		}
		StringBuilder sb = new StringBuilder();
		while(!stack.isEmpty()) {
			int tmp = stack.pop();
			sb.append(tmp);
		}
		return sb.toString();
	}
// 递归    
public String reverse(ListNode head) {
		if(head == null) return "";
		 return reverse(head.next) + head.val;
	}

相关文章

微信公众号

最新文章

更多