Java에서 증분 정렬 연결 목록 병합을 구현하는 방법

이 기사에서는 주로 오름차순 정렬 연결 목록 병합을 구현하는 Java 프로그래밍을 소개합니다. 코드는 도움이 필요한 친구들이 참조할 수 있도록 모든 사람과 공유됩니다.

문제 설명

단조 증가하는 연결 리스트 두 개를 입력하고, 두 개의 연결 리스트를 결합한 연결 리스트를 출력합니다. 물론 단조 비감소 규칙을 만족하려면 결합 연결 리스트가 필요합니다.

답변:

/* 
public class ListNode { 
  int val; 
  ListNode next = null; 
 
  ListNode(int val) { 
    this.val = val; 
  } 
}*/ 
public class Solution { 
  public ListNode Merge(ListNode list1,ListNode list2) { 
    if(list1==null)return list2; //判断到某个链表为空就返回另一个链表。如果两个链表都为空呢？没关系，这时候随便返回哪个链表，不也是空的吗? 
    if(list2==null)return list1; 
    ListNode list0=null;//定义一个链表作为返回值 
    if(list1.val<list2.val){//判断此时的值，如果list1比较小，就先把list1赋值给list0，反之亦然 
      list0=list1; 
      list0.next=Merge(list1.next, list2);//做递归，求链表的下一跳的值 
      } 
      else{ 
      list0=list2; 
      list0.next=Merge(list1, list2.next); 
      } 
 return list0; 
  } 
}

단순화하고 삼항 연산자를 사용하세요.

public class Solution {
	public ListNode Merge(ListNode list1,ListNode list2) {
		if(list1==null) 
		      return list2;
		if(list2==null) 
		      return list1;
		ListNode head;
		list0= list1.val>list2.val?list2:list1;
		list0.next = list1.val>list2.val?Merge(list1,list2.next):Merge(list1.next,list2);
		return list0;
	}
}

이 질문은 피보나치 수열 질문과 동일하기 때문에 인터뷰 중에 자주 테스트된다고 합니다. 재귀적 솔루션과 비재귀적 솔루션이 있습니다. 아래에서 비재귀적 솔루션에 대해 이야기해 보겠습니다.

/* 
public class ListNode { 
  int val; 
  ListNode next = null; 
  ListNode(int val) { 
    this.val = val; 
  } 
}*/
public class Solution {
	public ListNode Merge(ListNode list1,ListNode list2) {
		if(list1 == null) 
		        return list2;
		if(list2 == null ) 
		        return list1;
		ListNode tmp1 = list1;
		ListNode tmp2 = list2;
		ListNode head = new ListNode(0);
		//这里不能把返回链表赋值为null，因为下一行马上就要把它赋值给另一链表，得让它在内存里有位置才行 
		ListNode headptr = head;
		while(tmp1 != null && tmp2!=null){
			if(tmp1.val <= tmp2.val) 
			          {
				head.next=tmp1;
				head = head.next;
				tmp1 = tmp1.next;
			} else{
				head.next=tmp2;
				head = head.next;
				tmp2=tmp2.next;
			}
		}
		//其中一个链表已经跑到头之后，继续单链表的合并 
		while(tmp1 != null){
			head.next = tmp1;
			head = head.next;
			tmp1= tmp1.next;
		}
		while(tmp2 != null){
			head.next = tmp2;
			head = head.next;
			tmp2= tmp2.next;
		}
		head = headptr.next;
		return head;
	}
}

요약

위 내용은 Java에서 증분 정렬 연결 목록 병합을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!