Skip to content

PrintConSingleLinkList

Jump to bottom
PingWu edited this page Apr 13, 2016 · 1 revision

# 3.从尾到头打印链表

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

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

       思路:从头到尾遍历一遍链表，将每个结点顺次压入栈中。遍历完链表后，再从栈顶开始逐个输出结点的值。代码中的链表插入方法为头插法。具体头插法的介绍详见：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();
}

}       程序运行结果截图：

       
      链表构建部分参考：

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

Clone this wiki locally