Java linked list example analysis

1. Delete all nodes with value val

Delete all nodes in the linked list that are equal to the given value val. [OJ link]

Define two pointers prev and cur, cur points to the next node of the head node, and prev always points to the previous node of cur (convenient to delete nodes). Use the cur pointer to traverse the linked list and compare it with the val value. If it is the same, delete the node. Finally, compare the head nodes.

/**
 * 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. Reverse the linked list

Reverse a linked list. [OJ link]

#When traversing the linked list, change the pointer of the current node to point to the previous node. Since a node has no reference to its previous node, its previous node must be stored beforehand. The latter node also needs to be stored before changing the reference. Finally, the new header reference is returned.

/**
 * 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. Return the middle node of the linked list

Given a non-empty singly linked list with a head node, return the middle node of the linked list. If there are two intermediate nodes, the second intermediate node is returned. [OJ link]

We can define two fast and slow pointers (fast, slow), both pointing to the head node. The fast pointer takes two steps at a time, and the slow pointer takes one step at a time. When the linked list has an even number of nodes, slow is the intermediate node when fast=null; when the linked list has an odd number of nodes, slow is the intermediate node when 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. Return the K-th node in the linked list

Input a linked list and return the K-th node from the last in the linked list. [OJ link]

This question is similar to the idea of ​​finding the middle node. Define two pointers (fast, slow). Under the premise that K is reasonable, we can let the fast pointer go K-1 steps first, and then the fast and slow pointers move backward at the same time. When fast reaches the end of the linked list, slow points to the K-th node from the bottom.

/*
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. Merge ordered linked lists

Merge two ordered linked lists into one ordered linked list and return. The new linked list is formed by concatenating all the nodes of the two given linked lists. [OJ link]

#To solve this problem, you need to define a false node to serve as the head node of the new linked list. Traverse the two nodes through the head nodes of the two linked lists, compare the values ​​of the corresponding nodes of the two linked lists, and connect the node with the smaller value to the back of the new linked list. When the two linked lists are traversed, when one of the linked lists is empty, Just connect another linked list directly to the back of the new linked list.

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. Split the linked list by value

Divide a linked list into two parts according to a given value X. All nodes less than X are ranked before nodes greater than or equal to X. The original order of nodes is not changed. [OJ link]

First we need to define four pointers (bs, be, as, ae) to respectively represent the head node and tail node of the linked list smaller than X, and the head node and tail node of the linked list larger than X. Traverse the linked list through the head node and divide the linked list into two parts. Finally, connect the two linked lists. Special attention should be paid to that when the linked list less than X is not empty, we need to manually set ae.next to empty.

/*
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. Interpret the palindrome linked list

Determine whether the linked list is a palindrome linked list. [OJ link]

First we need to find the middle node of the linked list, and then reverse the second half of the linked list. Finally, just compare step by step through both sides. Pay special attention to that when the number of nodes in the linked list is an even number, because of the intermediate nodes, the two sides cannot meet when traversing, and special processing is required.

/*
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. Find the common node of two linked lists

Input two linked lists and output the two linked lists The first public node. No NULL is returned. [OJ link]

The intersection of two linked lists presents a Y shape. Then the difference in length of the two linked lists must be the difference between the two linked list nodes before they intersect. We need to find the length of the two linked lists. Define two pointers (pl, ps), let pl point to the long linked list, and ps point to the short linked list. Find the length difference len between the two linked lists. Make pl want to take len steps. In this way, the remaining lengths of the two linked lists are the same. At this time, the two pointers traverse two linked lists at the same time. If they point to the same point, the two linked lists intersect. Otherwise, the two linked lists do not intersect.

/**
 * 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. Determine whether there is a ring in the linked list

Determine whether there is a ring in the linked list. [OJ link]

is still a speed pointer. The slow pointer takes one step at a time, and the fast pointer takes two steps at a time. The two pointers start from the beginning of the linked list. If the linked list has a ring, they will definitely meet in the ring, otherwise the fast pointer will reach the end of the linked list first.

/**
 * 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. Return the entry of the ring linked list

Given a linked list, determine whether there is a ring in the linked list and return the node that enters the ring. If there is no cycle, NULL is returned. 【OJ link】

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

/**
 * 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;
    }
}

The above is the detailed content of Java linked list example analysis. For more information, please follow other related articles on the PHP Chinese website!