Algorithms – linked lists

Reverse a linked list

Leetcode-cn.com/problems/re…

    public ListNode reverseList(ListNode head) {
        / / iteration
        ListNode prev=null,next=null,curr=head;
        while(curr! =null){
            next=curr.next;
            curr.next=prev;
            prev=curr;
            curr=next;
        }
        return prev;
    }
Copy the code

Reverse linked list II

Leetcode-cn.com/problems/re…

    public ListNode reverseBetween(ListNode head, int left, int right) {
        / / head interpolation
        ListNode dummy = new ListNode(0);
        dummy.next=head;
        ListNode curr=head,prev=dummy;
        for(int i=0; i<left-1; i++){ prev=curr; curr=curr.next; }// Move the next node of the current node after the prev
        // Next always points to the next node of curr.
        ListNode next=null;

        for(int i=0; i<right-left; i++){ next=curr.next; curr.next=next.next; next.next=prev.next; prev.next=next; }return dummy.next;
    }
Copy the code

Flip linked lists in groups of K

Leetcode-cn.com/problems/re…

    public ListNode reverseKGroup(ListNode head, int k) {
        // iteration + recursion

        // Handle the boundary first
        if(head==null || head.next==null) {return head;
        }
        ListNode curr=head;
        ListNode tail=head;
        for(int i=0; i<k; i++){if(tail==null) {// If there are less than k bytes, return directly
                return head;
            }
            tail=tail.next;
        }

        ListNode node = reverse(head,tail);
        head.next= reverseKGroup(tail,k);
       
        return node;
    }
    
    public ListNode reverse(ListNode head,ListNode tail){
        ListNode prev=null,next=null,curr=head;
        while(curr! =tail){ next=curr.next; curr.next=prev; prev=curr; curr=next; }return prev;
    }
Copy the code

Circular linked list II

Leetcode-cn.com/problems/li…

    /** let the distance from head to intersection be a, the ring length be b, the slow pointer length be s, the fast pointer length be f, f=2s; f=s+nb; s=nb; So, if S takes another step, it will be right at the entrance of the ring. * /
    public ListNode detectCycle(ListNode head) {
        if(head==null) {return null;
        }
        ListNode p=head,q=head;
        while(q! =null&& q.next! =null){
            p=p.next;
            q=q.next.next;

            if(p==q){ // Find the intersection node
                while(head! =p){ head=head.next; p=p.next; }returnp; }}return null;
    }
Copy the code

Deletes the penultimate node of the linked list

Leetcode-cn.com/problems/re…

    public ListNode removeNthFromEnd(ListNode head, int n) {
        // The speed pointer
        ListNode dummy = new ListNode();
        dummy.next=head;
        ListNode prev=dummy,curr=head;
        for(int i=0; i<n; i++){ curr=curr.next; }while(curr! =null){
            curr=curr.next;
            prev=prev.next;
        }
        prev.next=prev.next.next;

        return dummy.next;
    }
Copy the code

List for peace

Leetcode-cn.com/problems/su…

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int a=0;
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;

        while(l1! =null|| l2! =null || a>0) {int x=l1==null?0:l1.val;
            int y=l2==null?0:l2.val;
            int sum=x+y+a;
            a=sum/10;
            int val=sum%10;

            l1=l1==null?null:l1.next;
            l2=l2==null?null:l2.next;

            ListNode node = new ListNode(val);
            prev.next=node;
            prev=prev.next;
        }
        return dummy.next;
    }
Copy the code

Merge K ascending linked lists

Leetcode-cn.com/problems/me…

    public ListNode mergeKLists(ListNode[] lists) {
        
        int n = lists.length;
        if(n==0) {return null;
        }
        if(n==1) {return lists[0];
        }

        int flag=n%2;
        int k=n/2;
        ListNode[] newList=new ListNode[k+flag];
        for(int i=0,j=0; i<k; i++){ ListNode node = merge(lists[j],lists[j+1]);
            newList[i]=node;
            j+=2;
        }
        if(flag==1){
            newList[k]=lists[n-1];
        }

        return mergeKLists(newList);

    }

    public ListNode merge(ListNode l1,ListNode l2){
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while(l1! =null&&l2! =null) {if(l1.val>l2.val){
                curr.next=l2;
                l2=l2.next;
            }else{
                curr.next=l1;
                l1=l1.next;
            }
            curr=curr.next;
        }
        if(l1! =null){
            curr.next=l1;
        }
        if(l2! =null){
            curr.next=l2;
        }
        return dummy.next;
    }
Copy the code

Sorting list

Leetcode-cn.com/problems/so…

    public ListNode sortList(ListNode head) {
        quickSort(head,null);
        return head;
    }

       public void quickSort(ListNode head,ListNode tail){

        if(head==null||head==tail){
            return ;
        }
        ListNode prev = null;
        ListNode left=head;
        ListNode right=head.next;
        int key=head.val;
        while(right! =tail){while(right! =null&&right! =tail && right.val>key){ right=right.next; }// Switch right and left nodes next
            if(right! =tail && left.next! =null&& right! =null){
                swap(left.next,right);
                prev=left;
                left=left.next;
                right=right.next;
            }

        }
        swap(head,left);
        quickSort(head,left);
        quickSort(left.next,tail);
    }

    public void swap(ListNode l1,ListNode l2){
        int temp=l1.val;
        l1.val=l2.val;
        l2.val=temp;
    }
Copy the code

Palindrome list

Leetcode-cn.com/problems/pa…

    public boolean isPalindrome(ListNode head) {
        ListNode fast=head,slow=head;
        while(fast! =null&&fast.next! =null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode node = reverse(slow);
        while(node! =null&&head! =null) {if(node.val! =head.val){return false;
            }
            node=node.next;
            head=head.next;
        }
        return true;
    }

    public ListNode reverse(ListNode head){
        ListNode curr=head,next=null,prev=null;
        while(curr! =null){
            next=curr.next;
            curr.next=prev;
            prev=curr;
            curr=next;
        }
        return prev;
    }
Copy the code

Delete duplicate element I from sorted linked list

Leetcode-cn.com/problems/re…

    public ListNode deleteDuplicates(ListNode head) {
        if(head==null) {return head;
        }
        ListNode curr=head;
        while(curr.next! =null) {if(curr.val==curr.next.val){
                curr.next=curr.next.next;
            }else{ curr=curr.next; }}return head;
    }
Copy the code

Delete duplicate element II from sorted linked list

Leetcode-cn.com/problems/re…

    public ListNode deleteDuplicates(ListNode head) {
        int preVal=101;
        ListNode dummy=new ListNode(101);
        dummy.next=head;
        ListNode prev=dummy, curr=head;
        while(curr! =null) {if(curr.val==preVal||(curr.next! =null&&curr.next.val==curr.val)){
                prev.next=curr.next;
            }else{
                prev=curr;
            }
            preVal=curr.val;
            curr=curr.next;
        }
        return dummy.next;
    }
Copy the code

Parity linked list

Leetcode-cn.com/problems/od…

    public ListNode oddEvenList(ListNode head) {
        if(head==null||head.next==null) {return head;
        }
        ListNode p=new ListNode(0);
        ListNode q=new ListNode(0);
        ListNode pHead=p;
        ListNode qHead=q;
        ListNode curr=head;
        int i=1;
        while(curr! =null) {if(i%2= =1){
                p.next=curr;
                p=p.next;
            }else{
                q.next=curr;
                q=q.next;
            }
            i++;
            curr=curr.next;
        }
        q.next=null;
        p.next=qHead.next;
        return pHead.next;
    }
Copy the code

Rearrange the list

Leetcode-cn.com/problems/re…

I don’t have to do it all, but remember

Split list

Leetcode-cn.com/problems/pa…

    public ListNode partition(ListNode head, int x) {
        if(head==null) {return head;
        }
        ListNode p= new ListNode(0);
        ListNode q= new ListNode(0);
        ListNode qHead=q,pHead=p;
        ListNode curr=head;
        while(curr! =null) {if(curr.val<x){
                p.next=curr;
                p=p.next;
            }else{
                q.next=curr;
                q=q.next;
            }
            curr=curr.next;
        }
        q.next=null;
        p.next=qHead.next;
        return pHead.next;
    }
Copy the code