Snap 1669 combine deux notes de liste

Voici deux listes. list1 Et list2 ,Ils contiennent les éléments suivants: n Et m - Oui..

S'il vous plaît list1 Indice moyen de a À b Tous les noeuds de,Et valist2 Connecté à l'emplacement du noeud supprimé.

Les bords bleus et les noeuds de l'image suivante montrent les résultats après l'opération：

Veuillez retourner le pointeur d'en - tête de la liste des résultats.

Exemple 1：

Entrée：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Produits：[0,1,2,1000000,1000001,1000002,5]
Explication：Nous supprimons list1 L'indice moyen est 3 Et 4 Deux noeuds de,Et va list2 Connectez - vous à cet endroit.Les bords bleus et les noeuds de l'image ci - dessus sont la liste des réponses.

Exemple 2：

Entrée：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
Produits：[0,1,1000000,1000001,1000002,1000003,1000004,6]
Explication：Les bords bleus et les noeuds de l'image ci - dessus sont la liste des réponses.

Source:：Boucle de force（LeetCode）
Liens：https://leetcode.cn/problems/merge-in-between-linked-lists
Le droit d'auteur est la propriété du réseau de saisie.Pour les réimpressions commerciales, veuillez contacter l'autorisation officielle,Reproduction non commerciale Veuillez indiquer la source.

  Il s'agit de supprimer un paragraphe d'une liste et d'en ajouter un autre.

Vous devez d'abord connaître le début et la fin de la suppression

Connectez l'extrémité de départ à l'extrémité de départ d'un autre segment après avoir trouvé l'extrémité de départ et l'extrémité d'extrémité , Connectez l'extrémité d'extrémité à l'extrémité d'un autre segment.

class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode before = list1, after = list1;
        //before Représentant la première moitié ,after Représentant la deuxième moitié 
        for (int i = 1; i < a; i++) {
            before = before.next;
        }
        //De1Àa-1Traversée（Totala-1Une fois） Trouver la tête du segment inséré 
        for (int i = 0; i <= b; i++) {
            after = after.next;
        }
        //De0ÀbTraversée（Totalb+1Une fois） Trouver la queue du segment inséré 
        ListNode begin = list2, end = list2;
        //beginReprésentantlist2Le début de,endReprésentantlist2Fin de
        while (end.next != null) {
            end = end.next;
        }
        // Trouver la queue du segment inséré , La tête de la deuxième moitié de la première liste 
        before.next = begin;
        end.next = after;
        // Fermeture séquentielle 
        return list1;
    }
}

Trouver une meilleure façon de résoudre le problème ,Comparaison des résultats, C'est une bonne idée. b Le noeud derrière le noeud est trouvé directement à la première fois a-1Le noeud commence, Les étapes répétées sont omises ,Peu de temps,Faible consommation de mémoire

class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode cur = list1;
        int count = b - a + 2;
        // Trouverlist1MoyenneaNoeud précédent des noeuds
        while ((a - 1) > 0) {
            a--;
            cur = cur.next;
        }
        ListNode left = cur;
        // Trouverlist1Moyenneb Noeud suivant des noeuds 
        while (count > 0) {
            cur = cur.next;
            count--;
        }
        ListNode right = cur; 
        // Oui.list1Moyennea Noeud précédent des noeuds pointant vers list2Noeud de tête de
        left.next = list2;
        // Trouverlist2Noeud de queue
        while(list2.next != null) {
            list2 = list2.next;
        }
        // Oui.list2 Le noeud de queue de list1Moyenneb Noeud suivant des noeuds 
        list2.next = right;
        return list1;
    }
}