[leetcode]- linked list-3

Preface

Record LeetCode Brush problems encountered in the linked list related problems , Third articles

206. Reverse a linked list

class Solution {
    
   public ListNode reverseList(ListNode head) {
    
       if(head == null){
    
           return null;
       }
        ListNode temp = head.next;
        head.next = null;
        // After the whole recursive process, the new head node after inversion will be returned 
        return recrution(head,temp);
    }
    // Recursive method , Invert two consecutive nodes each time node1 and node2 (node1 The forward part has been reversed ),
    // The specific operation is to record  node2 The next node behind , namely node2.next
    // And then node2.next Point to node1, Then keep going back yes node2 And what was saved at the beginning node2 At the start of the 
    // The next node calls the recursive method 
    public ListNode recrution(ListNode node1,ListNode node2) {
    
        if(node2 == null){
    
            return node1;
        }
        ListNode temp = node2.next;
        node2.next = node1;
        return recrution(node2,temp);
    }
}

25. K A set of flip list

First , The reverse part uses 206 The code of the question
Traverse the entire list , Every traversal K individual , Just put this K Cut it out separately , Then this linked list , At this time, we can get the new head node and tail node after inversion . We record the tail node obtained after reversing the previous paragraph lastTail, After each reversal , You can make lastTail Of next Point to the new head node of the segment after reversal , Then continue to traverse the rest of this paragraph

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
       if(head == null){
    
           return null;
       }
        ListNode temp = head.next;
        head.next = null;
        return recrution(head,temp);
    }
    public ListNode recrution(ListNode node1,ListNode node2) {
    
        if(node2 == null){
    
            return node1;
        }
        ListNode temp = node2.next;
        node2.next = node1;
        return recrution(node2,temp);
    }
    public ListNode reverseKGroup(ListNode head, int k) {
    
    	// Classic skills of linked list , Set a dummy node 
        ListNode dummy = new ListNode();
        ListNode lastTail = dummy; // Reverse the tail node obtained after the previous paragraph 
        ListNode nextHead = head;  // The head node of the next segment to be reversed 
        ListNode cur,tmp;
        int i;
        while(true){
    
            cur = nextHead;   //cur Used to traverse the linked list 
            for(i = 1;i < k && cur != null;i++){
    
                cur = cur.next;
            }
            if(cur == null || i < k){
    
                break;
            }
            tmp = cur.next; //tmp Used to record cur The next node of , That is, the head node of the linked list to be reversed in the next segment 
            cur.next = null; // Cut out this paragraph 
            reverseList(nextHead); // After reversing cur Is the new head node ,nextHead  Is the new tail node 
            lastTail.next = cur;
            lastTail = nextHead; // to update lastTail
            nextHead = tmp; // Update the header node of the next segment to be reversed 
        }
        // The number of nodes in the last segment may not meet  K  individual , In the above cycle, I received lastTail Back 
        // So jump out of the loop and connect 
        lastTail.next = nextHead;
        return dummy.next;
    }
}

92. Reverse a linked list II

General train of thought ： First create a dummy node dummy As a temporary header node . Variable tmp Traversing the linked list , When traversing to the original list left When the previous node of a node , Use one reversedTail Variable record left Nodes , This node will become the last node of the inverted linked list

Then I started to do the first left Reverse the linked list starting with nodes . When reverse to right When a node , use reversedTailNext Variable record right The next node of a node , This node is the next node of the inverted linked list segment . Then go back to right Nodes , Then the return value of the whole recursive method is the head node of the inverted linked list segment , Write it down as reversedHead

The last is the finishing work , Connect the inverted linked list segment with the original linked list
because tmp It is the first in the original list left The previous node of a node , therefore tmp The subsequent node strain of is reversedHead; then reversedTailNext What is saved is the next node of the inverted linked list segment ,reversedTail What is saved is the last node of the inverted linked list , So let reversedTail The successor node of becomes reversedTailNext. Connection work completed , return dummy.next that will do

class Solution {
    
    int count; // When the record is reversed, which node is it reversed to 
    ListNode reversedTailNext;  // Record the next node of the linked list after inversion 
    // The method of recursively reversing the linked list 
    ListNode rec(ListNode p1, ListNode p2,int right){
    
        if(count == right){
     
            reversedTailNext = p2;
            return p1;
        }
        ListNode tmp = p2.next;
        p2.next = p1;
        count++;
        return rec(p2,tmp,right);
    }
    public ListNode reverseBetween(ListNode head, int left, int right) {
    
        int cur = 1; // Record which node you are currently traversing 
        ListNode dummy = new ListNode(-1,head);
        ListNode tmp = dummy;
        while(cur++ < left){
    
            tmp = tmp.next;
        }
        count = left;
        ListNode reversedTail = tmp.next;
        ListNode reversedHead =  rec(tmp.next,tmp.next.next,right);
        tmp.next = reversedHead;
        reversedTail.next = reversedTailNext;
        return dummy.next;
    }
}

The finger of the sword Offer 22. Last in the list k Nodes

The first idea is to traverse the linked list to find the length of the linked list len, And then start from the beginning to find the first len - k + 1 The second node is the penultimate k Nodes

This requires two iterations , Complexity O(n + n). Do the problem of single chain table always think about whether you can solve the problem only once , The solution to this question is ： Since we are looking for the penultimate k Nodes , If there are two pointers p1 and p2,p1 before p2 After , Their distance is always k, So when p2 Point to the end of the linked list null When ,p1 It points to the penultimate k A node . So let's first p2 Go to No k + 1 Location of nodes , And then let p1 Start from scratch , The two pointers go back one step at a time , When p2 Go to the null When ,p1 The position of is the penultimate k Nodes

public ListNode getKthFromEnd(ListNode head, int k) {
    
    if(head == null) return null;
    ListNode p2 = head;
    int endP2 = k + 1; //p2  At the beginning, go to the  k + 1 Location of nodes 
    int count = 1; // Record  p2  The location of , At first, on the  1  Nodes 
    while(p2 != null && count < endP2){
    
        p2 = p2.next;
        count++;
    }
    if(p2 == null){
      // If at the end of the cycle  p2  Point to  null , according to count  Judge whether it is just the end or not  k  Nodes 
        if(count == endP2) return head;
        return null;
    }
    // And then let  p1  Start walking 
    ListNode p1 = head;
    while(p2 != null){
    
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}

19. Delete the last of the linked list N Nodes

The data of the title guarantees the penultimate N Nodes must exist , Then we just need to find the penultimate in the list N + 1 Nodes , Let it next The field is changed to the penultimate N Of nodes next that will do

Then the first step is to find the penultimate in the linked list N + 1 Nodes , See above The finger of the sword Offer 22. Last in the list k Just one node

public ListNode removeNthFromEnd(ListNode head, int n) {
    
    ListNode dummmy = new ListNode(-1,head);
    ListNode p1 = dummmy,p2 = dummmy;
    int count = n + 1;
    while(count-- > 0){
    
        p2 = p2.next;
    }
    while(p2 != null){
    
        p1 = p1.next;
        p2 = p2.next;
    }
    p1.next = p1.next.next;
    return dummmy.next;
}

148. Sort list

Using the idea of merge sort , Each time, the linked list segment is divided into two segments , Sort these two paragraphs separately , Then merge the sorted two linked list segments

public ListNode sortList(ListNode head) {
    
		// Recursive boundary 
        if(head == null || head.next == null) return head;
        ListNode slow = head,fast = head,tmp = slow;
        // Fast and slow double pointers find the first node of the next linked list and let slow Pointing to it . use tmp maintain slow The previous node of 
        while(fast != null && fast.next != null){
    
            fast = fast.next.next;
            tmp = slow;
            slow = slow.next;
        }
        // The front and back linked lists are disconnected 
        tmp.next = null;
        // The two linked lists are sorted separately 
        ListNode l1 =  sortList(head);
        ListNode l2 =  sortList(slow);
        ListNode dummy = new ListNode();
        tmp = dummy;
        // Merge list 
        while(l1 != null && l2 != null){
    
            if(l1.val < l2.val){
    
                tmp.next = l1;
                l1 = l1.next;
                tmp = tmp.next;
            }else{
    
                tmp.next = l2;
                l2 = l2.next;
                tmp = tmp.next;
            }
        }
        tmp.next = l1 == null ? l2 : l1;
        /*while(l1 != null){ tmp.next = l1; l1 = l1.next; tmp = tmp.next; } while(l2 != null){ tmp.next = l2; l2 = l2.next; tmp = tmp.next; }*/
        return dummy.next;
    }

24. Two or two exchange nodes in a linked list

swapPairs Method will head Exchange positions for the first and second nodes of the linked list of head nodes , Then return to the new header node , That is, the original head Next node of . Recursively exchange every two nodes as a group

public ListNode swapPairs(ListNode head) {
    
	//head by null Or there is only one node without exchange 
    if(head == null || head.next == null) return head;
    // Record the third node 
    ListNode tmp = head.next.next;
    // Exchange head nodes and secondary nodes 
    ListNode p1 = head,p2 = head.next;
    p2.next = p1;
    // Perform recursive operations on subsequent linked list segments 
    p1.next = swapPairs(tmp);
    return p2;
}

138. Copy list with random pointer

Based on the official solution, it is changed to a more understandable version ：
There is a one-to-one correspondence between the nodes of the original linked list and the new linked list , We can use a hash table map Store this correspondence , The key is a node in the original linked list , The value is the corresponding node in the new linked list

say concretely , For the original linked list o1->o2->o3->o4, Here we only consider next attribute . Then we can follow next Property to traverse the original linked list and create a new linked list , obtain n1->n2->n3->n4, Of the linked list node at this time random The field has not been set . At the same time, update in the process of creating a new linked list map, final map by {(o1,n1),(o2,n2),(o3,n3),(o4,n4)}

Then we go through the original list and the new list again , Put the random The field points to the corresponding node in the original linked list random The domain node acts as a key in map Corresponding value in . For example, specifically , After traversing to o1 as well as n1 when , Find out o1 Of random Domain is o3, that o3 stay map The corresponding value in is n3, therefore n1.random = n3, And so on

class Solution {
    
    HashMap<Node,Node> map = new HashMap<Node, Node>();
    public Node copyRandomList(Node head) {
    
        if (head == null) return null;
        //newHead It is the head node of the new linked list ,newCur Used to traverse the new linked list ,oldCur Used to traverse the original linked list 
        Node newHead = new Node(head.val),newCur = newHead,oldCur = head;
        map.put(oldCur,newCur);
        oldCur = oldCur.next;
        // Traverse the original list and create each node of the new list in turn 
        while(oldCur != null){
    
            newCur.next = new Node(oldCur.val);
            newCur = newCur.next;
            map.put(oldCur,newCur);
            oldCur = oldCur.next;
        }
        newCur.next = null; // Of the last node next Remember to set as null
        newCur = newHead;
        oldCur = head;
        // Traverse the two linked list pairs again random Set the value of the field 
        while(newCur != null){
    
            newCur.random = map.get(oldCur.random);
            newCur = newCur.next;
            oldCur = oldCur.next;
        }
        return newHead;
    }
}