Java实现链表及其上的相关操作

链表相关。头插法建立，尾插法建立，遍历，倒置，在有序的链表中插入一个数还是有序，在有序的链表中删除一个数还是有序，合并两个有序列表

Java实现链表及其相关操作，如下所示：

• 头插法
• 尾插法
• 遍历
• 倒置
• 在有序的链表中插入一个数还是有序
• 在有序的链表中删除一个数还是有序
• 合并两个有序列表

Node文件代码如下：

public class Node {
	Object data;
	Node next;
	
	public Object getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}
	
	public Node() {
		this.data = null;
	}
	
	public Node(int data) {
		this.data = data;
	}
	
	/**
	 * 头插法建立链表
	 * @param length 链表的长度，这里先设定初始长度
	 * @return 链表的头指针
	 */
	public Node createListF(int length) {
		Node head,s;
		head = new Node();
		head.next = null;
		
		for (int i=1; i<=length; i++) {
			s = new Node(i);
			s.next = head.next;
			head.next = s;
		}	
		
		return head;
	}
	
	/**
	 * 尾插法建立链表
	 * @param length 链表的长度，这里先设定初始长度
	 * @return 链表的头指针
	 */
	public Node createListR(int length) {
		Node head,rear,s;
		head = new Node();
		rear = head;
		
		for (int i=1; i<=length; i++) {
			s = new Node(i);
			rear.next = s;
			rear = s;
		}
		
		rear.next = null;
		
		return head;
	}
	
	public void traverseList(Node head) {
		Node p = head.next;
		
		while(p != null) {
			System.out.print(p.data + " ");
			p = p.next;
		}
		
		System.out.println();
		
	}
	
	/**
	 * 链表反转
	 * @param head 反转前链表的头指针
	 * @return head 反转后链表的头指针
	 */
	public Node reverseList(Node head) {
		Node p,q,temp;
		
		p = head.next;
		q = p.next;
		
		while (q != null) {
			temp = q.next;
			q.next = p;
			p = q;
			q = temp;
		}
		
		head.next.next = null;
		head.next = p;
		
		return head;
	}
	
	/**
	 * 在有序的链表中插入一个数还是有序
	 * @param head 插入前链表的头指针
	 * @param x 要插入的值
	 * @param asc 初始链表是否升序
	 * @return head 插入后链表的头指针
	 */
	public Node insertDataInOrderedList(Node head,int x,boolean asc) {
		Node p,s,q;
		q = head;
		p = q.next;
		
		if (asc) {
			//升序
			while ((p != null) && (Integer.parseInt(p.data == null?"":p.data.toString())) <= x) {
				q = p;
				p = p.next;
			}
			s = new Node(x);
			q.next = s;
			s.next = p;
			
			p = null;
			q = null;
		} else {
			while ((p != null) && (Integer.parseInt(p.data == null?"":p.data.toString())) >= x) {
				p = p.next;
				q = q.next;
			}
			s = new Node(x);
			q.next = s;
			s.next = p;
			
			p = null;
			q = null;
		}
		
		return head;
	}
	
	/**
	 * 在有序的链表中删除一个数还是有序
	 * @param head
	 * @param x
	 * @param asc
	 * @return
	 */
	public boolean deleteDataInOrderedList(Node head, int x,boolean asc) {
		Node p,q;
		q = head;
		p = q.next;
		
		while ((p != null) && (Integer.parseInt(p.data == null?"":p.data.toString())) != x) {
			q = p;
			p = p.next;
		}
		
		if(p == null) {
			return false;
		}
		
		q.next = p.next;
		
		p = null;
		q = null;
		
		return true;

	}
	
	/**
	 * 合并两个有序列表
	 * @param head1
	 * @param head2
	 * @return
	 */
	public Node mergeTwoOrderedList(Node head1,Node head2) {
		Node head,p1 = head1.next,p2 = head2.next; //p1,p2分别为head1,head2的游标
		head = new Node(); //生成头结点
		head.next = null;
		
		while (p1 != null && p2 != null) {
			if (objToInt(p1.data) <= objToInt(p2.data)) {
				head.addNodeAtTheEnd(head, objToInt(p1.data));
				p1 = p1.next;
			} else {
				head.addNodeAtTheEnd(head, objToInt(p2.data));
				p2 = p2.next;
			}
		}
		
		while(p1 != null) {
			head.addNodeAtTheEnd(head, objToInt(p1.data));
			p1 = p1.next;
		}
		
		while(p2 != null) {
			head.addNodeAtTheEnd(head, objToInt(p2.data));
			p2 = p2.next;
		}
		
		return head;
	}
	
	/**
	 * 在链表的末端追加元素
	 * @param head 原来链表的头指针
	 * @param x 所追加元素的值
	 * @return head 追加元素之后的链表的头指针
	 */
	public Node addNodeAtTheEnd(Node head,int x) {
		Node q = head,p = q.next;
		while (p != null) {
			q = p;
			p = p.next;
		}
		
		Node newNode = new Node(x);
		q.next = newNode;
		newNode.next = null;

		return head;
	}
	
	/**
	 * Object转化为int
	 * @param obj
	 * @return
	 */
	public int objToInt(Object obj) {
		return Integer.parseInt(obj == null ? "" : obj.toString());
	}
	
}

Test文件代码如下：

public class Test {

	public static void main(String[] args) {
		Node node = new Node();
		Node head = node.createListF(6);
		System.out.print("头插法建立的链表:");
		node.traverseList(head);
		
		System.out.print("反转后的链表:");
		head = node.reverseList(head);
		node.traverseList(head);
		
		System.out.print("插入值为4的数之后的链表:");
		head = node.insertDataInOrderedList(head, 4, true);
		node.traverseList(head);
		
		System.out.print("删除链表中第一个值为5的数，是否成功？");
		boolean isDeleted = node.deleteDataInOrderedList(head, 5, true);
		if (isDeleted) {
			System.out.print("已被删除！");
			System.out.println();
		}
		System.out.print("删除链表中第一个值为5的数之后的链表:");
		node.traverseList(head);
		
		System.out.print("新增值为10的结点:");
		node.addNodeAtTheEnd(head, 10);
		node.traverseList(head);
		
		Node newHead = node.createListR(10);
		System.out.print("原来的head链表:");
		node.traverseList(head);
		System.out.print("原来的newHead链表:");
		node.traverseList(newHead);
		Node mergeNode = node.mergeTwoOrderedList(head, newHead);
		System.out.println("Merge two linklist:");
		node.traverseList(mergeNode);
	}
}