剑指Offer 面试题5 从尾到头打印链表
本文题目来自《剑指offer 名企面试官精讲典型编程题》面试题5。
题目5：输入一个链表的头结点，从尾到头反过来打印每个结点的值。
思路:从头到尾遍历一遍链表，将每个结点顺次压入栈中。遍历完链表后，再从栈顶开始逐个输出结点的值。代码中的链表插入方法为头插法。具体头插法的介绍详见：http://blog.csdn.net/wp1603710463/article/details/50989500
Java实现代码：
1.SingleLinkList:
package list;2.TestSingleLinkList:
import java.util.HashSet;
import java.util.Set;
/**
* @author WuPing
* @version 2016年4月11日 上午10:41:43
*/
public class SingleLinkList {
class Element {
public Value value = null;
public Element nextNode = null;
}
class Value {
public long code;
public String name;
public Value() {
}
public Value(long code, String name) {
this.code = code;
this.name = name;
}
@Override
public String toString() {
return code + "-" + name;
}
}
private Element header = null;
public void add(Value node) {
if (header == null) {
header = new Element();
header.value = null;
header.nextNode = null;
}
Element element = new Element();
element.value = node;
element.nextNode = header.nextNode;
header.nextNode = element;
}
public void clear() {
header = null;
}
public boolean contains(Object o) {
if (header == null)
return false;
Element eqEl = header.nextNode;
while (eqEl != null) {
if (eqEl.value == o) {
return true;
}
eqEl = eqEl.nextNode;
}
return false;
}
public String toString() {
int size = this.size();
String print = "";
if (size == 0)
return print;
for (int i = 0; i < size; i++) {
print = "," + this.get(i) + print;
}
print = "[" + print.substring(1) + "]";
return print;
}
public Object get(int index) {
if (header == null)
return null;
int size = this.size();
if (index > (size - 1) || index < 0) {
return null;
}
Element temp = header.nextNode;
int i = 0;
while (temp != null) {
if (index == i) {
return temp.value;
}
i++;
temp = temp.nextNode;
}
return null;
}
public String getValueName(int index) {
if (header == null)
return "";
int size = this.size();
if (index > (size - 1) || index < 0) {
return "";
}
Element temp = header.nextNode;
int i = 0;
while (temp != null) {
if (index == i) {
return temp.value.name;
}
i++;
temp = temp.nextNode;
}
return "";
}
private Element getElement(int index) {
if (header == null)
return null;
int size = this.size();
if (index > (size - 1) || index < 0) {
return null;
}
Element temp = header.nextNode;
int i = 0;
while (temp != null) {
if (index == i) {
return temp;
}
i++;
temp = temp.nextNode;
}
return null;
}
public boolean isEmpty() {
if (header == null)
return true;
else
return false;
}
public boolean remove(Object o) {
if (header == null)
return false;
Element eqPreEl = header;
Element eqEl = header.nextNode;
while (eqEl != null) {
if (eqEl.value == o) {
eqPreEl.nextNode = eqEl.nextNode;
return true;
}
eqPreEl = eqEl;
eqEl = eqEl.nextNode;
}
return false;
}
public int size() {
if (header == null)
return 0;
Element temp = header.nextNode;
int i = 0;
while (temp != null) {
i++;
temp = temp.nextNode;
}
return i;
}
// 检查环状单链表
public boolean checkLoop() {
if (header == null)
return false;
int size = this.size();
if (size == 0)
return false;
Set<Element> set = new HashSet<Element>();
for (int i = 0; i < size; i++) {
Element el = getElement(i);
if (!set.contains(el)) {
set.add(el);
}
if (set.contains(el.nextNode)) {
return true;
}
}
return false;
}
}
package list;程序运行结果截图：
import list.SingleLinkList;
import list.SingleLinkList.Value;
import java.util.Stack;
/**
* @author WuPing
* @version 2016年4月11日 上午10:53:00
*/
public class TestSingleLinkList {
public static void Test1() {
System.out.println("1.链表有多个结点：");
SingleLinkList list = new SingleLinkList();
Value value1 = list.new Value(1, "Java");
Value value2 = list.new Value(2, "JavaScript");
Value value3 = list.new Value(3, "PHP");
Value value4 = list.new Value(4, "C++");
Value value5 = list.new Value(5, "Python");
Value value6 = list.new Value(6, "Swift");
//头插法插入链表
list.add(value1);
list.add(value2);
list.add(value3);
list.add(value4);
list.add(value5);
list.add(value6);
//用栈保存链表的结点值信息
System.out.print("正序打印链表结点的值:");
Stack<String> stack = new Stack<String>();
for(int i=0; i<list.size(); i++) {
System.out.print(" " + list.getValueName(i));
stack.push(list.getValueName(i));
}
System.out.println();
//逆序打印链表结点的值
System.out.print("逆序打印链表结点的值:");
while(!stack.empty()) {
String str = stack.pop();
System.out.print(" " + str);
}
System.out.println();
System.out.println("Remove Swift ? " + list.remove(value6));
System.out.println("Have C++ ? " + list.contains(value4));
System.out.println("List is emptry ? " + list.isEmpty());
System.out.println(list);
list.clear();
System.out.println("List is emptry ? " + list.isEmpty());
}
public static void Test2() {
System.out.println("2.链表只有一个结点：");
SingleLinkList list = new SingleLinkList();
Value value1 = list.new Value(1, "Java");
//头插法插入链表
list.add(value1);
//用栈保存链表的结点值信息
System.out.print("正序打印链表结点的值:");
Stack<String> stack = new Stack<String>();
for(int i=0; i<list.size(); i++) {
System.out.print(" " + list.getValueName(i));
stack.push(list.getValueName(i));
}
System.out.println();
//逆序打印链表结点的值
System.out.print("逆序打印链表结点的值:");
while(!stack.empty()) {
String str = stack.pop();
System.out.print(" " + str);
}
System.out.println();
}
public static void Test3() {
System.out.println("3.链表为空: ");
SingleLinkList list = new SingleLinkList();
//用栈保存链表的结点值信息
System.out.print("正序打印链表结点的值:");
Stack<String> stack = new Stack<String>();
for(int i=0; i<list.size(); i++) {
System.out.print(" " + list.getValueName(i));
stack.push(list.getValueName(i));
}
System.out.println();
//逆序打印链表结点的值
System.out.print("逆序打印链表结点的值:");
while(!stack.empty()) {
String str = stack.pop();
System.out.print(" " + str);
}
System.out.println();
}
public static void main(String[] args) {
Test1();
Test2();
Test3();
}
}
链表构建部分参考：
用Java语言实现单链表：http://www.cnblogs.com/junsky/archive/2010/05/16/1736563.html