リンクリスト よくある問題

こんにちは、みんな.今日は、リンクされたリストの一般的なタスクを分析します.
も確認できます.
リストの最初のタスクは、2 つのソート済みリストをマージすることです.

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.

この問題にどのようにアプローチしますか?リンクされたリストを操作するための最も一般的な手法の 1 つは、2 ポインターです.この場合、各リストの先頭をポインターとして使用し、一方が他方よりも大きい場合にのみ要素を移動できます.また、より長いリストの残りの要素で、結果のリストを補足することを忘れないでください.

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;
    }

次に、**Add Two Numbers **タスクにスムーズに進みます.

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 自体を除いて、2 つの数字に先頭のゼロが含まれていないと仮定することができます.
この場合、数値を追加する必要があります.ただし、金額が 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.

この問題を解決するための興味深いアプローチがいくつかあります. (私にとって)最も書きやすいものを分析します.このアプローチを書くのに時間はかかりません.私の考えは、私たちはノードを通り抜けているということです.ノードに子がある場合、子ソーダのリストが現在のリストに収まるようにリンクを再配置します.最悪の場合、子ノードを 2 回実行する必要があるというニュアンスがあります.

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;
    } 

このアルゴリズムはどのように改善できますか?子ノードに出会うと、リストの深さまで再帰的に進むことができます.最も深遠な子要素に到達したら、それを親に埋め込みます.視覚的には、以前のアルゴリズムとはまったく異なります.
ご不明な点がございましたら、喜んでお答えいたします.

かなり人気のある**奇偶連結リスト**タスクを忘れないでください.

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.

二人の走者の技を覚えられます.奇数要素と偶数要素に対して 2 つのノードを用意でき、それらを正常に追加できます.最後に、2 つのリストをマージする必要があります.どうやってするの?このためには、尾が必要です.したがって、下を埋めるときは、尾をずらします.そして最後に、テールオッドとヘッドイーブンを組み合わせます.

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;
    }