Analisis contoh senarai terpaut Java

1. Padam semua nod dengan nilai val

Padam semua nod dalam senarai terpaut yang sama dengan nilai yang diberikan. [Pautan OJ]

Tentukan dua penunjuk prev dan cur mata ke nod seterusnya nod kepala Prev sentiasa menunjuk ke nod cur sebelumnya (mudah untuk memadamkan nod). Gunakan penunjuk cur untuk melintasi senarai terpaut dan bandingkan dengan nilai val Jika ia sama, padamkan nod. Akhir sekali, bandingkan nod kepala.

/**
 * 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. Balikkan senarai terpaut

Balikkan senarai terpaut. [Pautan OJ]

Apabila melintasi senarai terpaut, tukar penuding nod semasa untuk menghala ke nod sebelumnya. Memandangkan nod tidak mempunyai rujukan kepada nod sebelumnya, nod sebelumnya mesti disimpan terlebih dahulu. Nod terakhir juga perlu disimpan sebelum menukar rujukan. Akhirnya, rujukan pengepala baharu dikembalikan.

/**
 * 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. Kembalikan nod tengah senarai terpaut

Memandangkan senarai terpaut tunggal yang tidak kosong dengan nod kepala, kembalikan nod tengah senarai terpaut. Jika terdapat dua nod perantaraan, nod perantaraan kedua dikembalikan. [Pautan OJ]

Kita boleh menentukan dua penunjuk cepat dan perlahan (cepat, perlahan), kedua-duanya menghala ke nod kepala. Penunjuk pantas mengambil dua langkah pada satu masa, dan penunjuk perlahan mengambil satu langkah pada satu masa. Apabila senarai terpaut mempunyai bilangan nod genap, nod perantaraan adalah lambat apabila fast=null apabila senarai terpaut mempunyai bilangan nod ganjil, nod perantaraan adalah lambat apabila fast.next=null.

/**
 * 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 Kembalikan nod Kth senarai terpaut

Masukkan senarai terpaut dan kembalikan nod Kth dari yang terakhir dalam senarai terpaut . [Pautan OJ]

Soalan ini serupa dengan idea mencari nod tengah. Tentukan dua penunjuk (cepat, perlahan). Di bawah premis bahawa K adalah munasabah, kita boleh membiarkan penunjuk pantas pergi ke langkah K-1 dahulu, dan kemudian penunjuk cepat dan perlahan bergerak ke belakang pada masa yang sama Apabila pantas mencapai penghujung senarai terpaut, perlahan menunjuk ke K -nod ke- dari bawah.

/*
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. Gabungkan senarai terpaut tersusun

Gabungkan dua senarai terpaut tersusun ke dalam satu senarai terpaut tersusun dan kembalikan. Senarai terpaut baharu dibentuk dengan menggabungkan semua nod dua senarai terpaut yang diberikan. [Pautan OJ]

Untuk menyelesaikan masalah ini, anda perlu menentukan nod palsu untuk berfungsi sebagai nod kepala senarai terpaut baharu. Lintas dua nod melalui nod kepala dua senarai terpaut, bandingkan nilai nod yang sepadan bagi dua senarai terpaut, dan sambungkan nod dengan nilai yang lebih kecil ke bahagian belakang senarai terpaut yang baharu senarai dilalui, apabila salah satu senarai terpaut kosong, Sambungkan senarai terpaut lain terus ke belakang senarai terpaut baharu.

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 Pisahkan senarai terpaut mengikut nilai

Bahagikan senarai terpaut kepada dua bahagian mengikut nilai X yang diberikan, dan semua nod yang kurang daripada X disenaraikan sebelum nod lebih besar daripada atau. sama dengan X. Susunan asal nod tidak diubah. [OJ link]

Mula-mula kita perlu mentakrifkan empat penunjuk (bs, be, as, ae) untuk masing-masing mewakili nod kepala dan nod ekor senarai terpaut yang lebih kecil daripada X, dan nod kepala dan nod ekor daripada senarai terpaut yang lebih besar daripada X. Lintas senarai terpaut melalui nod kepala dan bahagikan senarai terpaut kepada dua bahagian. Akhir sekali, sambungkan dua senarai terpaut. Perhatian khusus harus diberikan apabila senarai terpaut kurang daripada X tidak kosong, kita perlu menetapkan ae.sebelah kosong secara manual.

/*
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 Tafsiran senarai terpaut palindrom

Tentukan sama ada senarai terpaut ialah senarai terpaut palindrom. [OJ Link]

Mula-mula kita perlu mencari nod tengah senarai terpaut, dan kemudian membalikkan separuh kedua senarai terpaut. Akhir sekali, hanya bandingkan langkah demi langkah melalui kedua-dua belah pihak. Beri perhatian khusus apabila bilangan nod dalam senarai terpaut ialah nombor genap, kerana nod perantaraan, kedua-dua belah pihak tidak dapat bertemu apabila melintasi, dan pemprosesan khas diperlukan.

/*
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 Cari nod biasa dua senarai terpaut

Masukkan dua senarai terpaut dan keluarkan dua. Nod biasa pertama senarai terpaut. Tiada NULL dikembalikan. [Pautan OJ]

Persilangan dua senarai terpaut membentangkan bentuk Y. Kemudian perbezaan panjang dua senarai terpaut mestilah perbezaan antara dua nod senarai terpaut sebelum ia bersilang. Kita perlu mencari panjang dua senarai yang dipautkan. Tentukan dua petunjuk (pl, ps), biarkan pl menunjuk ke senarai terpaut panjang, dan ps menunjuk ke senarai terpaut pendek. Cari beza panjang len antara dua senarai berpaut. Buat pl nak ambil langkah len. Dengan cara ini, baki panjang kedua-dua senarai terpaut adalah sama. Pada masa ini, kedua-dua penunjuk merentasi dua senarai terpaut pada masa yang sama Jika ia menunjuk ke titik yang sama, kedua-dua senarai terpaut itu tidak bersilang.

/**
 * 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. Tentukan sama ada terdapat gelang dalam senarai terpaut

Tentukan sama ada terdapat gelang dalam senarai terpaut. [Pautan OJ]

Masih penunjuk kelajuan. Penunjuk perlahan mengambil satu langkah pada satu masa, dan penunjuk pantas mengambil dua langkah pada satu masa. Dua petunjuk bermula dari permulaan senarai terpaut. Jika senarai pautan mempunyai cincin, mereka pasti akan bertemu di gelanggang, jika tidak penunjuk pantas akan sampai ke penghujung senarai pautan terlebih dahulu.

/**
 * 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 Kembalikan entri senarai terpaut cincin

Memandangkan senarai terpaut, tentukan sama ada terdapat gelang dalam senarai terpaut dan kembalikan nod yang memasuki gelang. Jika tiada kitaran, NULL dikembalikan. 【Pautan 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;
    }
}

Atas ialah kandungan terperinci Analisis contoh senarai terpaut Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!