LeetCode探索中級[両数加算][パリティチェーンテーブル][交差チェーンテーブル]

チェーンテーブル
@[チェーンテーブル|ダブルポインタ]
チェーンテーブルの問題は比較的把握しやすい.配列の問題だけでなく、チェーンテーブルの問題にも適した「ダブルポインタ解法」を忘れないでください.
もう1つのリンクリストの問題を大幅に簡略化する方法は「Dummy node」ノードテクニックであり,Dummy Nodeとは実際には先頭ノードのポインタである.
1.両数加算
2つの非負の整数を表す2つの非空のチェーンテーブルが与えられる.ビット数は逆順序で格納され、各ノードには単一の数値しか格納されません.2つの数を加算して新しいチェーンテーブルを返します.数字0以外の2つの数字はゼロで始まると仮定できます.例:
入力:(2->4->3)+(5->6->4)出力:7->0->8理由:342+465=807
大体の考え方は

1 head指向ヘッダを定義し、last指向テール

2 firstタグの最初の遍歴を定義し、nextタグが現在10,

より大きいかどうか、および

3は、2つのチェーンテーブルが空の

を指すまで2つのチェーンテーブルを巡回する.

4最終判断nextが真lastがListNode(1)

を指す場合

5はhead

に戻る

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
        ListNode head ,last = new ListNode(0);
        ListNode listNode;
        head = last.next;

        boolean first = true;
        int sum;
        boolean next = false;

        while (l1!=null || l2!=null){
            listNode = new ListNode(0);
            if(next){
                if(l1 == null){
                    sum = l2.val + 1;
                }else if(l2 == null){
                    sum = l1.val + 1;
                }else {
                    sum = l1.val + l2.val + 1;
                }
            }else {
                if(l1 == null){
                    sum = l2.val;
                }else if(l2 == null){
                    sum = l1.val;
                }else {
                    sum = l1.val + l2.val;
                }
            }

            if(sum>9){
                listNode.val = sum%10;
                next = true;
            }else{
                listNode.val = sum;
                next = false;
            }
            
            if(first){
                head = listNode;
                first = false;
            }
            last.next = listNode;
            last = last.next;

            if(l1!=null)
                l1 = l1.next;
            if(l2!=null)
                l2 = l2.next;
        }
        
        if(next){
            last.next = new ListNode(1);
        }

        return head;
        
    }
}

2.パリティチェーンテーブル
単一チェーンテーブルを指定し、すべての奇数ノードと偶数ノードをそれぞれ並べます.ここで、奇数ノードと偶数ノードは、ノードの値のパリティではなく、ノード番号のパリティを指すことに注意してください.その場のアルゴリズムで完了してみてください.あなたのアルゴリズムの空間複雑度はO(1)、時間複雑度はO(nodes)、nodesはノードの総数です.
例1:入力:1->2->3->4->5->NULL出力:1->3->5->2->4->NULL
例2:入力:2->1->3->5->6->4->7->NULL出力:2->3->6->7->1->5->4->NULL
説明:奇数ノードと偶数ノードの相対順序を維持する必要があります.チェーンテーブルの最初のノードは奇数ノードとみなされ、2番目のノードは偶数ノードとみなされます.
大体の考え方は

1はtempAが奇数チェーンテーブルを指し、tempBが偶数チェーンテーブル

を指すことを定義する.

2 headB指向tempBを定義する後、奇数チェーンテーブルの末尾指向双鎖テーブルのヘッダ

を容易に巡回する.

3チェーンテーブルが空の2つのチェーンテーブルに割り当てられるまでチェーンテーブルを巡回する

.

4最後にtempBを使用する.nextは空を指し、tempA.nextはheadB

を指す

5はhead

に戻る

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head ==null || head.next == null){
            return head;
        }
        
        ListNode tempA = head;
        ListNode tempB = head.next;
        
        ListNode headB = tempB;
        
        int x = 0;
        for(ListNode temp = head.next.next;temp!=null;temp = temp.next){
            if(x%2==0){
                tempA.next = temp;
                tempA = tempA.next;
            }else{
                tempB.next = temp;
                tempB = tempB.next;
            }
            x++;
        }
        tempB.next = null;
        tempA.next = headB;
        
        return head;
    }
}

3.交差チェーンテーブル
2つの単一チェーンテーブルが交差する開始ノードを見つけるプログラムを作成します.たとえば、次の2つのチェーンテーブルがあります.
A: ........a1 → a2 ........................↘ ..........................c1 → c2 → c3 ........................↗ B:b 1→b 2→b 3はノードc 1で交差し始める.
注意:

1両チェーンテーブルに交点がない場合nullを返す.

2結果が返された後も、2つのチェーンテーブルは元の構造を維持しなければならない.

3は、チェーンテーブル構造全体にループがないと仮定することができる.

4プログラムは、O(n)時間の複雑さをできるだけ満たし、O(1)メモリのみを使用する.

大体の考え方は

はlenAを定義し、lenBは2つのチェーンテーブル長

を表す.

2定義listは、2つのうち長いチェーンテーブル

を表す.

3リストを後ろに行かせますabs(lenA-lenB)ステップ

4はlist 2が短いチェーンテーブルを指すことを定義し、同時に2つのチェーンテーブル

を遍歴する.

5ループ中のlistがlist 2に等しい場合、listを返します.そうでない場合、head

を返します.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null && headB==null){
            return null;
        }
        
        int lenA = 0;
        int lenB = 0;
        
        for(ListNode temp = headA;temp!=null;temp = temp.next){
            lenA++;
        }
        for(ListNode temp = headB;temp!=null;temp = temp.next){
            lenB++;
        }
        
        boolean isA = lenA>lenB?true:false;
        
        ListNode list = isA?headA:headB;
        
        for(int x = 0; x

まとめ

チェーンテーブルの問題では、二重ポインタの問題

によく遭遇する.

チェーンテーブルにおける注意判定空ポインタ

フィードバックと提案

QQ:[3441242166]

メールボックス:[email protected]