Java 연결리스트 예시 분석

1. 값이 val인 모든 노드를 삭제합니다.

연결된 리스트에서 주어진 값인 val과 동일한 모든 노드를 삭제합니다. [OJ 링크]

prev와 cur 두 포인터를 정의하고, cur는 헤드 노드의 다음 노드를 가리키고, prev는 항상 cur의 이전 노드를 가리킵니다(노드 삭제에 편리함). cur 포인터를 사용하여 연결된 목록을 탐색하고 값이 동일하면 노드를 삭제합니다. 마지막으로 헤드 노드를 비교합니다.

/**
 * 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. 연결 목록의 중간 노드를 반환합니다.

헤드 노드가 있는 비어 있지 않은 단일 연결 목록이 있으면 연결 목록의 중간 노드를 반환합니다. 두 개의 중간 노드가 있는 경우 두 번째 중간 노드가 반환됩니다. [OJ 링크]

두 개의 빠른 포인터와 느린 포인터(빠른 포인터, 느린 포인터)를 정의할 수 있으며 둘 다 헤드 노드를 가리킵니다. 빠른 포인터는 한 번에 두 단계씩 이동하고, 느린 포인터는 한 번에 한 단계씩 이동합니다. 연결된 목록에 짝수 개의 노드가 있는 경우 fast=null일 때 느린 노드는 중간 노드입니다. 연결된 목록에 홀수 개의 노드가 있는 경우 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. 연결리스트의 K번째 노드를 반환합니다

연결리스트를 입력하고 연결리스트의 마지막 K번째 노드를 반환합니다. [OJ링크]

이 질문은 중간 노드를 찾는 아이디어와 비슷합니다. 두 개의 포인터(빠름, 느림)를 정의합니다. 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. 정렬된 연결 목록 병합

두 개의 정렬된 연결 목록을 하나의 정렬된 연결 목록으로 병합하고 반환합니다. 새로운 연결리스트는 주어진 두 연결리스트의 모든 노드를 연결하여 형성됩니다. [OJ 링크]

이 문제를 해결하려면 새로운 연결 리스트의 헤드 노드 역할을 할 거짓 노드를 정의해야 합니다. 두 개의 연결된 리스트의 헤드 노드를 통해 두 개의 노드를 순회하고, 두 개의 연결된 리스트의 해당 노드의 값을 비교하여, 두 개의 연결된 리스트가 연결되면 더 작은 값을 갖는 노드를 뒤쪽에 연결합니다. 목록을 순회할 때 연결 목록 중 하나가 비어 있으면 다른 연결 목록을 새 연결 목록의 뒷면에 직접 연결하면 됩니다.

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에 따라 두 부분으로 나누고, X보다 작은 모든 노드는 X보다 크거나 같은 노드보다 먼저 순위가 지정됩니다. 노드의 원래 순서는 변경되지 않습니다. [OJ 링크]

먼저 X보다 작은 연결 리스트의 헤드 노드와 테일 노드, 연결 리스트의 헤드 노드와 테일 노드를 각각 나타내기 위해 4개의 포인터(bs, be, as, ae)를 정의해야 합니다. X보다 크다. 헤드 노드를 통해 연결된 목록을 탐색하고 연결된 목록을 두 부분으로 나눕니다. 마지막으로 두 연결리스트를 연결합니다. 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 링크]

먼저 연결 리스트의 중간 노드를 찾은 다음 연결 리스트의 후반부를 반전시켜야 합니다. 마지막으로 양측을 단계별로 비교하십시오. Linked List의 노드 수가 짝수인 경우 중간 노드로 인해 순회 시 양측이 만날 수 없으므로 특별한 처리가 필요하므로 특히 주의하십시오.

/*
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. 두 연결리스트의 공통노드를 찾아보세요

두 연결리스트를 입력하고 두 연결리스트의 첫 번째 공통노드를 출력합니다. NULL이 반환되지 않습니다. [OJ 링크]

두 연결리스트의 교차점은 Y자 모양을 나타냅니다. 그런 다음 두 연결 목록의 길이 차이는 두 연결 목록 노드가 교차하기 전의 차이여야 합니다. 두 연결리스트의 길이를 구해야 합니다. 두 개의 포인터(pl, ps)를 정의하고 pl이 긴 연결 목록을 가리키고 ps가 짧은 연결 목록을 가리키도록 합니다. 두 연결리스트 사이의 길이 차이 len을 구합니다. pl이 한 단계 더 나아가고 싶게 만드세요. 이런 방식으로 두 연결리스트의 나머지 길이는 동일합니다. 이때 두 포인터는 두 연결리스트를 동시에 순회합니다. 동일한 지점을 가리키면 두 연결리스트가 교차하고 그렇지 않으면 두 연결리스트는 교차하지 않습니다.

/**
 * 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 링크]

여전히 속도 포인터입니다. 느린 포인터는 한 번에 한 단계씩 이동하고, 빠른 포인터는 한 번에 두 단계씩 이동합니다. 두 포인터는 연결된 목록의 시작 부분에서 시작됩니다. 연결된 목록에 링이 있으면 반드시 링에서 만날 것입니다. 그렇지 않으면 빠른 포인터가 연결된 목록의 끝에 먼저 도달합니다.

/**
 * 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!