Java リンクリストの例の分析-＆＃＆チュートリアル-php.cn

1. 値 val を持つすべてのノードを削除します。

指定された値 val に等しいリンクリスト内のすべてのノードを削除します。 [OJ リンク]

2 つのポインター prev と cur を定義します。cur はヘッドノードの次のノードを指し、prev は常に cur の前のノードを指します (ノードの削除に便利です)。 cur ポインタを使用してリンクリストを走査し、val 値と比較し、同じであればノードを削除します。最後に、ヘッドノードを比較します。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return null;
        }
        ListNode prev=head;
        ListNode cur=head.next;
        while(cur!=null){
            if(cur.val==val){
                prev.next=cur.next;
                cur=cur.next;
            }else{
                prev=cur;
                cur=cur.next;
            }
        }
        if(head.val==val){
            head=head.next;
        }
        return head;
    }
}

ログイン後にコピー

2. リンクリストを反転します

リンクリストを反転します。 [OJ リンク]

Java リンクリストの例の分析

#リンクリストを移動するときは、現在のノードのポインタが前のノードを指すように変更します。ノードは前のノードへの参照を持たないため、その前のノードを事前に格納する必要があります。後者のノードも参照を変更する前に保存する必要があります。最後に、新しいヘッダー参照が返されます。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode cur=head.next;
        head.next=null;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }
}

ログイン後にコピー

3. リンクリストの中間ノードを返す

ヘッドノードを持つ空ではない単一リンクリストが与えられた場合、リンクリストの中間ノードを返します。中間ノードが 2 つある場合は、2 番目の中間ノードが返されます。 [OJ リンク]

2 つの高速ポインタと低速ポインタ (高速、低速) を定義でき、両方ともヘッドノードを指します。高速ポインタは一度に 2 ステップを実行し、低速ポインタは一度に 1 ステップを実行します。リンクリストのノード数が偶数の場合、fast=null の場合、slow が中間ノードになります。リンクリストのノード数が奇数の場合、fast.next=null の場合、slow が中間ノードになります。

Java リンクリストの例の分析

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}

ログイン後にコピー

4. リンクリストの K 番目のノードを返す

リンクリストを入力し、リストの最後から K 番目のノードを返します。リンクされたリスト。 [OJ リンク]

この質問は、中間ノードを見つけるというアイデアに似ています。 2 つのポインター (高速、低速) を定義します。 K が妥当であるという前提の下では、最初に高速ポインタを K-1 ステップ移動させ、次に高速ポインタと低速ポインタを同時に後方に移動させることができます。高速がリンクリストの最後に到達すると、低速は K をポイントします。 -下から番目のノード。

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(k<=0||head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(k-1>0){
            if(fast.next==null){
                return null;
            }
            fast=fast.next;
            //先让快节点走k-1步
            k--;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
       
    }
}

ログイン後にコピー

5. 順序付きリンクリストをマージする

2 つの順序付きリンクリストを 1 つの順序付きリンクリストにマージし、戻ります。新しいリンクリストは、指定された 2 つのリンクリストのすべてのノードを連結することによって形成されます。 [OJ リンク]

Java リンクリストの例の分析

# この問題を解決するには、新しいリンクリストのヘッドノードとして機能する偽ノードを定義する必要があります。 2 つのリンクリストの先頭ノードを介して 2 つのノードをたどり、2 つのリンクリストの対応するノードの値を比較し、値が小さい方のノードを新しいリンクリストの後ろに接続します。リンクリストの 1 つが空の場合、リストを走査する場合は、別のリンクリストを新しいリンクリストの後ろに直接接続するだけです。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        //创建虚拟节点，充当新链表的头节点，值不代表任何意义
        ListNode node=new ListNode(-1);
        ListNode cur=node;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                cur.next=list1;
                list1=list1.next;
            }else{
                cur.next=list2;
                list2=list2.next;
            }
            cur=cur.next;
        }
        if(list1==null){
            cur.next=list2;
        }else{
            cur.next=list1;
        }
        return node.next;
    }
}

ログイン後にコピー

6. リンクリストを値で分割する

指定された値 X に従って、リンクリストを 2 つの部分に分割します。X 未満のすべてのノードは、X 以上のノードの前にランク付けされます。。ノードの元の順序は変更されません。 [OJ リンク]

まず、X より小さいリンクリストの先頭ノードと末尾ノード、および先頭ノードと末尾ノードをそれぞれ表す 4 つのポインター (bs、be、as、ae) を定義する必要があります。 X より大きいリンクリスト。ヘッドノードを介してリンクリストをトラバースし、リンクリストを 2 つの部分に分割します。最後に、2 つのリンクされたリストを接続します。 X 未満のリンクリストが空でない場合は、ae.next を手動で空に設定する必要があることに特別な注意を払う必要があります。

Java リンクリストの例の分析

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        if(pHead==null){
            return null;
        }
        ListNode bs=null;
        ListNode be=null;
        ListNode as=null;
        ListNode ae=null;
        ListNode cur=pHead;
        while(cur!=null){
            if(cur.val<x){
                if(bs==null){
                    bs=cur;
                    be=cur;
                }else{
                    be.next=cur;
                    be=cur;
                }
            }else{
                if(as==null){
                    as=cur;
                    ae=cur;
                }else{
                    ae.next=cur;
                    ae=cur;
                }
            }
            cur=cur.next;
        }
        if(bs==null){
            return as;
            //如果小于X部分为空，则直接返回大于X部分即可。此时ae.next一定为null
        }
        be.next=as;//否则连接小于X和大于X部分
        if(as!=null){
           ae.next=null;
           //当小于X部分不为空时，ae.next可能不为null，需要手动置为null
        }
        return bs;
    }
}

ログイン後にコピー

7. 回文リンクリストを解釈する

リンクリストが回文リンクリストかどうかを判断します。 [OJ リンク]

まず、リンクリストの中間ノードを見つけてから、リンクリストの後半を反転する必要があります。最後に、両側を段階的に比較してください。リンクリストのノード数が偶数の場合、中間ノードがあるため、トラバース時に両側が交わることがなく、特別な処理が必要になることに特に注意してください。

Java リンクリストの例の分析

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        if(A==null){
            return false;
        }
        if(A.next==null){
            return true;
        }
        //求链表的中间节点
        ListNode slow=A;
        ListNode fast=A;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //反转后半段链表
        ListNode cur=slow.next;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        //判断回文链表
        while(slow!=A){
            if(slow.val!=A.val){
              return false;
           }
            if(A.next==slow){
                return true;
            }
            slow=slow.next;
            A=A.next;
        }
        return true;
    }
}

ログイン後にコピー

8. 2 つのリンクリストの共通ノードを見つける

2 つのリンクリストを入力し、2 つのリンクされたリストを出力しますlist 最初のパブリックノード。 NULL は返されません。 [OJ リンク]

2 つのリンクされたリストの交差部分は Y 字型を表します。この場合、2 つのリンクリストの長さの差は、交差する前の 2 つのリンクリストノード間の差である必要があります。 2 つのリンクされたリストの長さを見つける必要があります。 2 つのポインター (pl、ps) を定義します。pl は長いリンクリストを指し、ps は短いリンクリストを指します。 2 つのリンクされたリストの長さの差 len を求めます。 pl が len 歩進みたいようにします。このようにして、2 つのリンクされたリストの残りの長さは同じになります。このとき、2 つのポインタは 2 つのリンクリストを同時に横断し、同じ点を指していれば 2 つのリンクリストは交差し、そうでない場合は 2 つのリンクリストは交差しません。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    //求链表长度
    public int len(ListNode head){
        int len=0;
        while(head!=null){
            head=head.next;
            len++;
        }
        return len;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        ListNode pl=headA;
        ListNode ps=headB;
        int lenA=len(headA);
        int lenB=len(headB);
        int len=lenA-lenB;
        if(len<0){
            //pl指向长的链表，ps指向短的链表
            pl=headB;
            ps=headA;
            len=-len;
        }
        while(len--!=0){
            pl=pl.next;
        }
        while(pl!=null){
            if(pl==ps){
                return pl;
            }
            pl=pl.next;
            ps=ps.next;
        }
        return null;
    }
}

ログイン後にコピー

9. リンクリストにリングがあるかどうかを判断します

リンクリストにリングがあるかどうかを判断します。 [OJ リンク]

は依然として速度ポインターです。低速ポインタは一度に 1 ステップを実行し、高速ポインタは一度に 2 ステップを実行します。 2 つのポインターは、リンクされたリストの先頭から始まります。リンクされたリストにリングがある場合、それらは必ずリング内で出会います。そうでない場合、高速ポインタは最初にリンクされたリストの末尾に到達します。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null){
            return false;//链表为空或者只有一个节点时，没有环
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
                //如果快慢节点可以相遇，表示链表有环
            }
        }
        return false;
    }
}

ログイン後にコピー

10. リングのリンクリストのエントリを返す

リンクリストが与えられた場合、リンクリストにリングがあるかどうかを判断し、リングに入るノードを返します。サイクルがない場合はNULLが返されます。【OJリンク】

让一个指针从链表的其实在位置开始遍历，同时另一个指针从上题中两只真相与的位置开始走，两个指针再次相遇时的位置肯定为环的入口

Java リンクリストの例の分析

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    //判断链表是否有环，并返回第一次快慢节点相交的位置
    public ListNode hasCycle(ListNode head){
         if(head==null||head.next==null){
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
               return slow;
            }
        }
        return null;
    }
    //当返回的结点与头节点再次相交时，为环的入口
    public ListNode detectCycle(ListNode head) {
        ListNode node=hasCycle(head);
        if(node==null){
            return null;
        }else{
            while(head!=node){
                head=head.next;
                node=node.next;
            }
        }
        return head;
    }
}

ログイン後にコピー

以上がJava リンクリストの例の分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。