`

将两个整型有序单向链表合成一个有序表

 
阅读更多
思路一:新建一个头节点,将原来的两个链表的节点依次插入到新节点之后~
(也有其他的思路,比如不新建一个头节点,直接在原来的基础之上进行交换,但是感觉思路以及实现上面没有第一个思路来得清晰简单。 以后再实现吧~)

一个bug 如果两个链表中有一个为空时 此时会出错
解决思路: 就检测第一个链表。如果为空,则直接返回第二个链表。无论第二个是否为空都行。


这个是节点

public class IntNode {
	int value;
	IntNode next;
	
	public IntNode(int value, IntNode next) {
		this.value = value;
		this.next = next;
	}
}



以下是main()方法
public class ListMerge {
	public static void main(String[] args) {
		//Linked List Construction
		
		IntNode a1 = new IntNode(1, null);
		IntNode a2 = new IntNode(2, null);
		IntNode a3 = new IntNode(7, null);
		
		IntNode b1 = new IntNode(3, null);
		IntNode b2 = new IntNode(4, null);
		IntNode b3 = new IntNode(8, null);
		
		a1.next = a2;
		a2.next = a3;
		b1.next = b2;
		b2.next = b3;
		
		IntNode head1 = a1;
		IntNode head2 = b1;
		
		//temp variables
		IntNode t = null;
		
		//create new head
		IntNode head = null;
		if(head1.value < head2.value) {
			head = head1;
			head1 = head1.next;
		} else {
			head = head2;
			head2 = head2.next;
		}
		head.next = null;
		t = head;
		
		
		//merge into new linked list
		while( head1 != null && head2 != null ) {
			if(head1.value < head2.value) {
				t.next = head1;
				head1 = head1.next;
			} else {
				t.next = head2;
				head2 = head2.next;
			}
			t = t.next;
			t.next = null;
		}
		
		//merge left ones
		if(head1 != null) {
			t.next = head1;
		} else if(head2 != null){
			t.next = head2;
		}
		
		//free space
		head1 = null;
		head2 = null;
		
		//print all nodes
		t = head;
		while(t != null) {
			System.out.print(t.value + " ");
			t = t.next;
		}
	}
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics