一道关于链表的面试题不会~有人能帮个忙吗解答下吗谢谢

问答首页 → 综合技术

0 0

一道关于链表的面试题不会~有人能帮个忙吗解答下吗谢谢5

3. 请给出一个单链表结构的定义，每个节点用来储存一个整型数，并且给出一段代码来合并两个已经按照该整数从小到大排好序的链表，使得合并后的链表也是同样排好序的。

数据结构

2008年8月21日 19:03

random
20
0 0 0

2个答案按时间排序按投票排序

0 0

采纳的答案

链表好久不用了，到现在只用数组和哈希表。

2008年8月21日 23:03

花花公子
376
0 0 0

添加评论

0 0

package pkg;

public class Node implements Comparable {
	private Integer value;
	private Node next;
	
	public Node(){
	}
	
	public Node(Integer value, Node next) {
		this.value = value;
		this.next = next;
	}
	
	public Node getNext() {
		return next;
	}
	public void setNext(Node next) {
		this.next = next;
	}
	public Integer getValue() {
		return value;
	}
	public void setValue(Integer value) {
		this.value = value;
	}
	public int compareTo(Object o) {
		Node another = (Node) o;
		return value.compareTo(another.getValue());
	}
}

package pkg;

public class IntegerList {
	
	public IntegerList() {
		first = null;
		size = 0;
	}
	
	public void add(Node node) {
		if(isEmpty()) {
			first = node;
			size = 1;
		} else {
			privateAddNode(node);
			size++;
		}
	}
	
	public boolean isEmpty() {
		return first == null;
	}
	
	public Node getFirst() {
		return first;
	}
	
	public int size() {
		return size;
	}
	
	private void privateAddNode(Node node) {
		Node currentNode = null, priorNode = null;
		
		if(first.compareTo(node) >= 0) {
			node.setNext(first);
			first = node;
			return;
		}
		
		priorNode = first;
		currentNode = first.getNext();
		
		while(currentNode != null) {
			
			if(currentNode.compareTo(node) >= 0) {
				priorNode.setNext(node);
				node.setNext(currentNode);
				return;
			}
			
			priorNode = currentNode;
			currentNode = currentNode.getNext();
		}
		
		priorNode.setNext(node);
		node.setNext(null);
	}
	
	
	
	private Node first;
	private int size;
}

package pkg;

public class Test {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		IntegerList list1 = new IntegerList();
		list1.add(new Node(Integer.valueOf(4), null));
		list1.add(new Node(Integer.valueOf(5), null));
		list1.add(new Node(Integer.valueOf(1), null));
		list1.add(new Node(Integer.valueOf(3), null));
		
		IntegerList list2 = new IntegerList();
		list2.add(new Node(Integer.valueOf(-3), null));
		list2.add(new Node(Integer.valueOf(5), null));
		list2.add(new Node(Integer.valueOf(100), null));
		list2.add(new Node(Integer.valueOf(100), null));
		list2.add(new Node(Integer.valueOf(-3), null));
		
		
		Node node = list2.getFirst();
		while(node != null) {
			int value = node.getValue().intValue();
			list1.add( new Node(Integer.valueOf(value), null) );
			node = node.getNext();
		}
		
		node = list1.getFirst();
		while(node != null) {
			System.out.println(node.getValue());
			node = node.getNext();
		}
		
		
	}

}

控制台打印：
-3
-3
1
3
4
5
5
100
100

2008年8月22日 07:06