Flip the linked list ii[three ways to flip the linked list +dummyhead/ head insertion / tail insertion]

Preface

There are two angles to flip the linked list , Three ways . The first angle , Flip the chain from the original list , Or the node pointing to the previous record , Recursive , Recyclable . Second angle , You don't have to work hard on the original list to complete it , use dummyHead Unified empty linked list / The first node operates , Insert the required nodes into the header ( Flip )/ The tail interpolation ( Find the nodes that meet the requirements ) Link nodes to the back .

One 、 Flip the middle part of the linked list

Two 、dummyHead& The first interpolation & The tail interpolation

1、 A scan + Flip list ( Another scan )

//  Reverse a linked list II
public class ReverseBetween {
    
    /* target： Flip the specified part of the linked list .  Split the middle part directly , Flip again , Connect again . */
    public ListNode reverseBetween(ListNode head, int left, int right) {
    
        //  Unified empty linked list / Operation of the first node .
        ListNode dummyHead = new ListNode(0, head);
        //  Count 
        int cnt = 1;
        //  Generate intermediate chain 
        ListNode p = dummyHead;
        ListNode begin = null, end = null, newHead = null, newTail = null;
        while (p.next != null) {
    
            if (cnt == left) {
    
                begin = p;
                newHead = p.next;
            }
            if (cnt == right) {
    
                end = p.next.next;
                newTail = p.next;
                p.next.next = null;
                break;
            }
            ++cnt;
            p = p.next;
        }
        //  Flip list 
        reverseList(newHead);
        //  Splicing list 
        begin.next = newTail;
        newHead.next = end;
        //  Back to the list 
        return dummyHead.next;
    }

    //  except for, Recursion is also possible / Insert the head , common 3 An angle solution . One is the list , Class is to reproduce and combine nodes into a new chain .
    private void reverseList(ListNode head) {
    
        ListNode pre = null;
        while (head != null) {
    
            ListNode next = head.next;
            head.next = pre;

            pre = head;
            head = next;
        }
    }

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

2、 A scan & The first interpolation & The tail interpolation （ Advanced ）

//  Advanced ： A scan .
class ReverseBetween2 {
    
    /* target： Flip the specified part of the linked list .  A scan , Turn over the matching place . */
    public ListNode reverseBetween(ListNode head, int left, int right) {
    
        //  Unified empty linked list / Operation of the first node .
        ListNode dummyHead = new ListNode();
        ListNode newHead = dummyHead,tail = dummyHead;
        //  There is no need to flip / The nodes that need to be flipped are interpolated by tail / The first interpolation 
        //  Count 
        int cnt = 1;
        while (head != null) {
    
            //  Take nodes 
            ListNode node = head;
            //  Update next head
            head = head.next;
            //  The first interpolation 
            if (left <= cnt && cnt <= right) {
    
                node.next = newHead.next;
                newHead.next = node;
                //  Determine whether to update the tail node .
                if (tail == dummyHead) tail = tail.next;
            }
            //  The tail interpolation 
            else {
    
                //  The tail interpolation , Need to update the header 
                newHead = node;
                //  Insert node 
                node.next = null;
                tail.next = node;
                tail = tail.next;
            }
            //  Update went there .
            ++cnt;
        }
        //  Back to the list 
        return dummyHead.next;
    }


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

summary

1）dummy Use of nodes , Make it easy to operate the linked list , Cooperate with the upper insertion / Tail insertion , Can play with linked list operation .

reference

[1] LeetCode Flip list II