剑指Offer 面试题5 从尾到头打印链表

た入场券 2022-07-26 12:17 147阅读 0赞

本文题目来自《剑指offer 名企面试官精讲典型编程题》面试题5。

题目5：输入一个链表的头结点，从尾到头反过来打印每个结点的值。

思路:从头到尾遍历一遍链表，将每个结点顺次压入栈中。遍历完链表后，再从栈顶开始逐个输出结点的值。代码中的链表插入方法为头插法。具体头插法的介绍详见：[http://blog.csdn.net/wp1603710463/article/details/50989500][http_blog.csdn.net_wp1603710463_article_details_50989500]

Java实现代码：

1.SingleLinkList:

package list;
    
    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;
        }
    
    }

2.TestSingleLinkList:

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();
        }
        
    }

程序运行结果截图：

![Center][]  
链表构建部分参考：

用Java语言实现单链表：[http://www.cnblogs.com/junsky/archive/2010/05/16/1736563.html][http_www.cnblogs.com_junsky_archive_2010_05_16_1736563.html]

[http_blog.csdn.net_wp1603710463_article_details_50989500]: http://blog.csdn.net/wp1603710463/article/details/50989500
[Center]: /images/20220724/d34244c20e7e40d8a76bb448143e070e.png
[http_www.cnblogs.com_junsky_archive_2010_05_16_1736563.html]: http://www.cnblogs.com/junsky/archive/2010/05/16/1736563.html