연결 목록 인기 있는 문제

여러분, 안녕하세요. 오늘은 연결 리스트에 대한 인기 있는 작업을 분석할 것입니다.
또한 확인할 수 있습니다.
목록의 첫 번째 작업은 두 개의 정렬된 목록 병합입니다.

You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.

이 문제에 어떻게 접근합니까? 연결 목록 작업에 가장 널리 사용되는 기술 중 하나는 두 포인터입니다. 우리의 경우 각 목록의 시작을 포인터로 사용하고 하나가 다른 것보다 큰 경우에만 요소를 이동할 수 있습니다. 또한 결과 목록을 더 긴 목록의 나머지 요소로 보충하는 것을 잊지 마십시오.

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode empty = new ListNode();
        ListNode emptyHead = empty;

        while(list1 != null && list2 != null) {
            if(list1.val > list2.val) {
                empty.next = list2;
                list2 = list2.next;
                empty = empty.next;
            } else {
                empty.next = list1;
                list1 = list1.next;
                empty = empty.next;
            }
        }

        while (list1 != null) {
            empty.next = list1;
            list1 = list1.next;
            empty = empty.next;
        }
        while (list2 != null) {
            empty.next = list2;
            list2 = list2.next;
            empty = empty.next;
        }
        return emptyHead.next;
    }

다음으로 **두 개의 숫자 추가 **작업으로 원활하게 이동합니다.

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

숫자 0 자체를 제외하고 두 숫자에 선행 0이 포함되어 있지 않다고 가정할 수 있습니다.
우리의 경우 숫자를 추가해야 합니다. 그러나 금액이 10을 초과하는 상황이 있을 수 있습니다. 그런 다음 잔액을 다음 작업으로 이체하는 것이 좋습니다. 합이 10인 경우도 있습니다. 그런 다음 별도의 경우에 꺼내거나 10보다 큰 조건과 결합할 수 있습니다.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode rezNodeHead = new ListNode();
        ListNode rezNode = rezNodeHead;
        int rest = 0;
        while (l1 != null || l2 != null) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;

            int rez = rest + val1 + val2;
            ListNode tmp = new ListNode();
            if (rez == 10) {
                tmp.val = 0;
                rezNode.next = tmp;
                rezNode = tmp;
                rest = 1;
            } else if (rez > 10) {
                int val = rez % 10;
                rest = rez / 10;
                tmp.val = val;
                rezNode.next = tmp;
                rezNode = tmp;
            } else {
                tmp.val = rez;
                rezNode.next = tmp;
                rezNode = tmp;
                rest = 0;
            }
            l1 = (l1 != null) ? l1.next : null;
            l2 = (l2 != null) ? l2.next : null;
        }
        if (rest != 0) {
            ListNode tmp = new ListNode();
            tmp.val = rest;
            rezNode.next = tmp;
        }
        return rezNodeHead.next;
    }

_ 이 문제에 대해 질문이 있으면 기꺼이 답변해 드리겠습니다._
다중 수준 이중 연결 목록을 평면화하는 방법은 없습니다. 이 작업에서 노드는 자식 노드를 가질 수 있습니다.

You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.

Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear after curr and before curr.next in the flattened list.

Return the head of the flattened list. The nodes in the list must have all of their child pointers set to null.

이 문제를 해결하기 위한 몇 가지 흥미로운 접근 방식이 있습니다. 나는 (나를 위해) 쓰기 가장 쉬운 것을 분석할 것이다. 이 접근 방식을 작성하는 데 오랜 시간이 걸리지 않습니다. 내 생각은 우리가 노드를 통해 실행되고 있다는 것입니다. 노드에 자식이 있으면 자식 탄산음료가 있는 목록이 현재 목록에 맞도록 링크를 다시 정렬합니다. 최악의 경우 자식 노드를 두 번이나 실행해야 한다는 뉘앙스가 있습니다.

public static Node flatten(Node head) {
        Node headTmp = head;
        if (head == null) {
            return head;
        }

        while (head != null) {
            Node child = head.child;
            Node next = head.next;

            if (child != null) {
                head.next = child;

                while (child.next != null) {
                    child = child.next;
                }
                child.next = next;
                next.prev = child;
            }
            head.child = null;
            head = head.next;
        }
        return headTmp;
    } 

이 알고리즘을 어떻게 개선할 수 있습니까? 자식 노드를 만나면 목록의 깊이까지 재귀적으로 들어갈 수 있습니다. 가장 심오한 자식 요소에 도달하면 부모에 포함됩니다. 시각적으로 이전 알고리즘과 완전히 다르게 보일 것입니다.
질문이 있으시면 기꺼이 답변해 드리겠습니다.

다소 인기 있는 **Odd-Even Linked List **작업을 잊지 마세요.

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.
The first node is considered odd, and the second node is even, and so on.
Note that the relative order inside both the even and odd groups should remain as it was in the input.
You must solve the problem in O(1) extra space complexity and O(n) time complexity.

두 주자의 기술을 기억할 수 있습니다. 홀수 및 짝수 요소에 대해 두 개의 노드를 준비할 수 있으며 성공적으로 추가합니다. 결국 우리는 두 개의 목록을 병합해야 합니다. 그것을 하는 방법? 이를 위해서는 꼬리가 필요합니다. 따라서 아래를 채울 때 꼬리를 이동합니다. 그리고 마지막에 꼬리 홀수와 머리 짝수를 결합합니다.

public ListNode oddEvenList(ListNode head) {
        if (head == null){
            return head;
        }
        ListNode oddHead = null;
        ListNode oddTail = null;
        ListNode evenHead = null;
        ListNode evenTail = null;
        int counter = 0;

        while(head != null) {
            counter += 1;
            if (counter % 2 != 0) {
                if (oddHead == null) {
                    oddHead = head;
                    oddTail = head;

                } else {
                    oddTail.next = head;
                    oddTail = head;
                }
            } else {
                if (evenHead == null) {
                    evenHead = head;
                    evenTail = head;

                } else {
                    evenTail.next = head;
                    evenTail = head;
                }
            }
            head = head.next;
        }

        oddTail.next = evenHead;
        if (evenTail != null){
            evenTail.next = null;
        }
        return oddHead;
    }