最新消息:热烈庆祝IT小记上线!

合并链表

package test;

import java.util.Arrays;

import test.Test3.Node;


public class Test2 {
	
	static class Node{
		int value = -1;
		Node next = null;
		public Node(int i){
			value = i;
		}
		
		@Override
		public String toString() {
			return value+"";
		}
	}
	
	static void mergeChain(Node h,Node h2){
		Node n1_pre = h;
		Node n21_pre = h2;
		Node n1 = h.next;
		Node n21 = h2.next;
		while(n1!=null && n21!=null){		
			if(n1.value>n21.value){
				n21_pre.next = n21.next;//n21脱离h2								
				n1_pre.next = n21;//n21加入h
				n21.next = n1;
				n21 = n21_pre.next;//修改当前h2指针 							
			}else{
				n1_pre = n1;		
				n1 = n1.next;		
			}
		}

		if(n21!=null){	
			n1_pre.next = n21;
			h2.next = null;
		}
		Node n = h.next;
		while(n!=null){
			System.out.println(n);		
			n = n.next;
		}		
	}
	
	public static void main(String[] args) {		
		Node head = new Node(-1);
		Node n1 = new Node(2);
		head.next = n1;
		Node n2 = new Node(4);
		n1.next = n2;
		Node n3 = new Node(7);
		n2.next = n3;
		Node n4 = new Node(8);
		n3.next = n4;
		
		Node head2 = new Node(-1);
		Node n21 = new Node(1);
		head2.next = n21;
		Node n22 = new Node(2);
		n21.next = n22;
		Node n23 = new Node(6);
		n22.next = n23;
		Node n24 = new Node(9);
		n23.next = n24;
		
		mergeChain(head,head2);		
	}
}

猜您喜欢

备案号:苏ICP备12016861号-4