LeetCodeブラシノート-19.チェーンテーブルの最後からN番目のノードを削除する(ダブルポインタ法)

タイトル:チェーンテーブルを指定し、チェーンテーブルの最後からn番目のノードを削除し、チェーンテーブルのヘッダノードに戻ります.例:
チェーンテーブルが与えられる:1->2->3->4->5、およびn=2.最後から2番目のノードを削除すると、チェーンテーブルは1->2->3->5になります.
説明:与えられたn保証は有効である.ステップアップ:1回のスキャンを使用して問題解を実現する:まずチェーンテーブルを1回遍歴してチェーンテーブルの長さを得て、最後からn番目のノード、すなわち正数のlen-n+1番目のノードを削除して、削除すればいい:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int len=0;
        ListNode temp=new ListNode();
        temp=head;
        while(temp!=null){
            temp=temp.next;
            len++;
        }
        temp=head;
        if(len==n) return head.next;//                  
        for(int i=0;i<len-n-1;i++){
            temp=temp.next;
        }
        temp.next=temp.next.next;
        return head;
    }
}

あるいは、削除する要素をダブルポインタ法で1回遍歴することができます.1番目のポインタはリストの先頭からn+1ステップ前進し、2番目のポインタはリストの先頭から出発する.ここで,この2つのポインタはn個のノードによって分離される.2つのポインタを同時に前に移動することによって,この一定の間隔を第1のポインタが最後のノードに達するまで維持した.2番目のポインタは、最後のノード数からn番目のノードを指します.2番目のポインタが参照するノードのnextポインタは、そのノードの次のノードを指します.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int len=0;
        ListNode temp1=new ListNode(0);
        ListNode temp2=new ListNode(0);
        temp1=head;
        temp2=head;
        while(len!=n){
            temp1=temp1.next;
            len++;
        }
        if(temp1==null) return head.next;
        while(temp1.next!=null){
            temp1=temp1.next;
            temp2=temp2.next;
        }
        temp2.next=temp2.next.next;
        return head;
    }
}

実際には、特殊な状況の干渉を減らすために(例えば、1つのノードだけを削除するには、最初のノードを削除する)、私たちは1つのノードを補助として採用することができます.ノードのnextこそheadノードです.具体的な考え方は公式解を参照してください.