Java에서 간단하고 최적의 방법으로 두 개의 정렬된 연결 목록을 병합합니다.

정렬된 두 개의 연결 목록을 병합하는 것은 효율적으로 해결할 수 있는 일반적인 문제입니다. Java를 사용하여 간단하고 최적의 방법으로 이를 수행할 수 있는 방법은 다음과 같습니다.

단계:

1. 더미 노드 생성: 더미 노드를 사용하면 병합 프로세스를 단순화할 수 있습니다. 이 노드는 병합된 목록의 시작 역할을 합니다.
2. 노드 비교: 두 연결 목록의 현재 노드를 비교합니다. 병합된 목록에 더 작은 노드를 연결하고 해당 목록의 포인터를 앞으로 이동합니다.
3. 남은 노드 처리: 한 목록이 다른 목록보다 먼저 소진되면 소진되지 않은 목록의 나머지 노드를 병합된 목록에 연결합니다.
4. 병합 목록 반환: 병합 목록은 더미 노드 옆의 노드부터 시작됩니다.

자바 구현:

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedList {

    // Function to merge two sorted linked lists
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Create a dummy node to act as the starting point
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // Traverse both lists and compare nodes
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        // If one list is exhausted, link the remaining nodes of the other list
        if (l1 != null) {
            current.next = l1;
        } else {
            current.next = l2;
        }

        // The merged list starts from the next node of the dummy node
        return dummy.next;
    }

    // Function to print the linked list
    public void printList(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Create first sorted linked list: 1 -> 3 -> 5
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);

        // Create second sorted linked list: 2 -> 4 -> 6
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);

        System.out.println("First List:");
        list.printList(l1);

        System.out.println("Second List:");
        list.printList(l2);

        // Merge the two lists
        ListNode mergedList = list.mergeTwoLists(l1, l2);

        System.out.println("Merged List:");
        list.printList(mergedList);
    }
}

설명:

1. ListNode 클래스:

   • 연결된 목록의 각 노드를 정수 값(val)과 다음 노드(next)에 대한 포인터로 나타냅니다.

2. mergeTwoLists 메서드:

   • 더미 노드: 더미 노드(dummy)는 시작점을 제공하여 병합 프로세스를 단순화하는 데 사용됩니다.
   • 비교 루프: 연결된 목록을 모두 탐색하여 현재 노드를 비교합니다. 더 작은 노드가 병합된 목록에 추가되고 해당 목록의 다음 노드로 이동합니다.
   • 남은 노드: 목록 중 하나가 소진된 후 다른 목록의 나머지 부분을 병합된 목록에 직접 첨부합니다.
   • Return: 마지막으로 더미 노드 옆의 노드부터 병합된 목록이 시작됩니다.

3. printList 메소드:

   • 이 유틸리티 함수는 쉽게 시각화할 수 있도록 연결 목록의 모든 노드를 인쇄합니다.

4. 주 메소드:

   • 2개의 정렬된 연결 목록 만들기: 예: 1 -> 3 -> 5와 2 -> 4 -> 6.
   • 목록 병합: 병합된 목록은 1 -> 2 -> 3 -> 4 -> 5 -> 6.
   • 목록 인쇄: 병합 전과 후의 효과를 확인하세요.

복잡성:

• 시간 복잡도: ( O(n + m) ), 여기서 (n )과 (m )은 두 연결 목록의 길이입니다. 두 목록의 각 노드는 정확히 한 번만 처리됩니다.
• 공간 복잡도: ( O(1) ), 몇 개의 포인터 외에는 추가 공간이 사용되지 않습니다.

이 방법은 두 개의 정렬된 연결 목록을 병합하는 데 간단하면서도 최적이며 효율적이고 깔끔한 코드를 보장합니다.

위 내용은 Java에서 간단하고 최적의 방법으로 두 개의 정렬된 연결 목록을 병합합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!