JAva実装---単一チェーンテーブルの最後からK番目のノードを検索し、チェーンテーブルを1回しか遍歴できないことを要求する;チェーンテーブルの最後からk番目のノードを削除

JAva実装

単一チェーンテーブルの最後からK番目のノードを検索するには、チェーンテーブル

を1回しか巡回できないことが要求される.

チェーンテーブルの最後からk番目のノード

を削除する.
単一チェーンテーブルの最後からK番目のノードを検索するには、チェーンテーブルを1回だけ巡回する必要があります.
2つの前後ノードforwardとbackward を定義する
まずforwardをk歩歩かせ、forwardをbackwardと一緒に歩かせ、forwardが空になるとbackwardは最後のk歩まで歩いた.

class ListNode{
    int data;
    ListNode next;
}
public class Link{
    public static void FindTailK(ListNode first,int k){
        ListNode forward = first;
        ListNode backward = first;
        while(k-- != 0){
            forward = forward.next;
        }
        while(forward != null){
            forward = forward.next;
            backward = backward.next;
        }
        System.out.println(backward.data);
    }
    public static void main(String[] args) {
        ListNode n1 = new ListNode();
        ListNode n2 = new ListNode();
        ListNode n3 = new ListNode();
        ListNode n4 = new ListNode();
        ListNode n5 = new ListNode();
        n1.data = 1;
        n2.data = 2;
        n3.data = 3;
        n4.data = 4;
        n5.data = 5;
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        FindTailK(n1,2);
    }
}

チェーンテーブルの最後からk番目のノードを削除
最後からk番目のノードを削除するには、最後からk+1番目のノード、すなわちkの前のノードを見つけることができる.
第2のステップは、kの前のノードのnextをkの後のノードに向ける.
すなわちkノードは削除するに相当する.

public class Link{
    public static ListNode DeleteTailK(ListNode first,int k){
        ListNode forward = first;
        ListNode backward = first;
        while(k-- != 0){
            forward = forward.next;
        }
        while(forward.next != null){   //    backward k      
            forward = forward.next;
            backward = backward.next;
        }
        backward.next = backward.next.next;
        return first;

    }
        public static void print(ListNode head){
        while(head != null){
            System.out.println(head.data);
            head = head.next;
        }
   }