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

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 リンク]

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

/**
 * 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 が中間ノードになります。

/**
 * 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 リンク]

# この問題を解決するには、新しいリンク リストのヘッド ノードとして機能する偽ノードを定義する必要があります。 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 を手動で空に設定する必要があることに特別な注意を払う必要があります。

/*
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 リンク]

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

/*
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リンク】

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

/**
 * 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 サイトの他の関連記事を参照してください。