Linked list review!

Single chain list

A linked list is a linear structure connected in series by pointers , Each node consists of two parts , One is the data field and the other is the pointer field （ Holds a pointer to the next node ）, The pointer field of the last node points to null（ A null pointer means ）. The entry node of the link is called the head node of the linked list head.

Double linked list

Double linked list ： Each node has two pointer fields , One points to the next node , One points to the previous node .
Double linked list You can query forward or backward .

Circular linked list

Circular linked list , seeing the name of a thing one thinks of its function , The linked list is connected end to end . Circular linked list can be used to solve Joseph ring problem .

How to store linked lists

Arrays are continuously distributed in memory , But linked lists are not continuously distributed in memory . Linked lists are made by Pointer to pointer field Link nodes in memory .

Definition of 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; }
 * }

Operation of linked list

Delete node , Add a node ----> The addition and deletion of the linked list are O(1) operation
But be careful , If you delete the fifth node , You need to find the fourth node from the beginning through next Pointer to delete , The time complexity of the search is O(n)

203. Remove linked list elements

subject

Give you a list of the head node head And an integer val , Please delete all the contents in the linked list Node.val == val The node of , And back to New head node .
Example ：

You can set up a virtual head node , In this way, all nodes in the original linked list can be removed in a unified way

Code

/** * 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) {
    
        ListNode dummy = new ListNode(-1); 
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        while(cur != null){
    
            if(cur.val == val){
    
                pre.next = cur.next;
            }else{
    
                pre = cur;
            }
            cur = cur.next;
        }
        return dummy.next;     
    }
}

707. Design the list

subject

  Design the realization of linked list . You can choose to use single or double linked list . Nodes in a single chain table should have two properties ：val  and  next.val  Is the value of the current node ,next  Is a pointer to the next node / quote . If you want to use a two-way linked list , Then you need an attribute  prev  To indicate the last node in the list . Suppose that all nodes in the list are  0-index  Of .

Implement these functions in the linked list class ：
get(index)： Get the index Values of nodes . If the index is invalid , Then return to -1.
addAtHead(val)： Add a value of... Before the first element of the list val The node of . After inserting , The new node will be the first node in the list .
addAtTail(val)： Will be worth val To the last element of the list .
addAtIndex(index,val)： In the list, the index The value added before nodes is val The node of . If index It's equal to the length of the list , Then the node will be attached to the end of the list . If index Greater than the length of the list , The node will not be inserted . If index Less than 0, Then insert the node in the head .
deleteAtIndex(index)： If the index index It works , Delete the index Nodes .
Example ：

Code

// Definition of linked list 
public class ListNode{
    
    int val;
    ListNode next;
    ListNode(){
    }
    ListNode(int val){
    
        this.val = val;
    } 
}
class MyLinkedList {
    
    int size; // The length of the list 
    ListNode dummy; // Virtual node 
    public MyLinkedList() {
    
        size = 0;
        dummy = new ListNode(0);
    }
    
    public int get(int index) {
    
        if(index >= size || index < 0)  return -1;
        ListNode cur = dummy;
        for(int i = 0; i <= index; i++){
    
            cur = cur.next;    
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
    
        addAtIndex(0,val);  
    }
    
    public void addAtTail(int val) {
    
        addAtIndex(size,val);

    }
    
    public void addAtIndex(int index, int val) {
    
        if(index > size) return;
        if(index < 0)  index = 0;
        size++;   
        // First find the precursor node of the inserted node 
        ListNode pre = dummy;
        for(int i = 0; i < index; i++){
    
            pre = pre.next;
        }
        ListNode toAdd = new ListNode(val);
        toAdd.next = pre.next;
        pre.next = toAdd;
    }
    
    public void deleteAtIndex(int index) {
    
        if(index >= size || index < 0)  return;
        // Find the precursor node that needs to be deleted 
        ListNode pre = dummy;
        for(int i = 0; i < index; i++){
    
            pre = pre.next;
        }
        pre.next = pre.next.next;
        size--;
    }
}

/** * Your MyLinkedList object will be instantiated and called as such: * MyLinkedList obj = new MyLinkedList(); * int param_1 = obj.get(index); * obj.addAtHead(val); * obj.addAtTail(val); * obj.addAtIndex(index,val); * obj.deleteAtIndex(index); */

206. Reverse a linked list

Here's the head node of the list head , Please reverse the list , And return the inverted linked list .

Code

/** * 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) {
    
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = null;

        while(cur != null){
    
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

24. Two or two exchange nodes in a linked list

subject

I'll give you a list , Two or two exchange the adjacent nodes , And return the head node of the linked list after exchange . You must complete this problem without modifying the value inside the node （ namely , Only node switching can be performed ）.

Code

/** * 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 swapPairs(ListNode head) {
    
        if(head == null) return head;

        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode pre = dummy;
        ListNode cur = head;
        ListNode temp = null;

        while(pre.next != null && pre.next.next != null){
    
            temp = cur.next.next;
            pre.next = cur.next;
            cur.next.next = cur;
            cur.next = temp;
            pre = cur;
            cur = temp;
        }
        return dummy.next;
    }
}

19. Delete the last of the linked list N Nodes

subject

I'll give you a list , Delete the last of the linked list n Nodes , And return the head node of the list .
Example ：

Code

/** * 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; } * } */
/** * 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 removeNthFromEnd(ListNode head, int n) {
    
       ListNode dummy = new ListNode(-1);
       dummy.next = head;
       ListNode slow = dummy;
       ListNode fast = dummy;
       ListNode pre = dummy;

       while(n-- > 0){
    
           fast = fast.next;
       }
       while( fast != null ){
    
           pre = slow;
           slow = slow.next;
           fast = fast.next;    
        }
        pre.next = pre.next.next;
        return dummy.next;
    }
}

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

subject

Enter a linked list , Output the last number in the list k Nodes . In order to conform to the habits of most people , From 1 Start counting , That is, the tail node of the list is the last 1 Nodes .
for example , A list has 6 Nodes , Start from the beginning , Their values, in turn, are 1、2、3、4、5、6. The last of the list 3 Each node has a value of 4 The node of .
Example ：

Code

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
    
    public ListNode getKthFromEnd(ListNode head, int k) {
    
        // Double pointer  former  and  latter
        //former Go ahead first k Step ; then former and latter Went together 
        // Special situations to consider ：1. Linked list is empty.  2. k = 0 3. k Value ＞ The length of the list 
        if(head == null || k==0)  return null;
        ListNode former = head, latter = head;
        for(int i = 0; i < k; i++){
    
            // explain k Value ＞ The length of the list 
            if(former == null)  return null;
            former = former.next;
        }
        while(former != null){
    
            former = former.next;
            latter = latter.next;
        }
        return latter;    
    }
}

Interview questions 02.07. The list intersects

Here are two head nodes of the single linked list headA and headB , Please find out and return the starting node where two single linked lists intersect . If there is no intersection between two linked lists , return null .
Figure two linked lists at the node c1 Start meeting ：

Subject data Guarantee There is no ring in the whole chain structure .
Example ：

Code

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
        ListNode A = headA, B = headB;
        while(A != B){
    
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;        
    }
}

141. Circular list

subject

Give you a list of the head node head , Judge whether there are links in the list .
If there is a node in the linked list , It can be done by continuously tracking next The pointer reaches again , Then there is a ring in the linked list . To represent a ring in a given list , The evaluation system uses an integer pos To indicate where the end of the list is connected to the list （ Index from 0 Start ）. Be careful ：pos Not passed as an argument . Just to identify the actual situation of the linked list . If there are rings in the list , Then return to true . otherwise , return false .
Example ：

Code

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
// Defining the  fast  and  slow The pointer , Start from the beginning ,fast The pointer moves two nodes at a time ,slow The pointer moves one node at a time , If  fast  and  slow The hands meet on the way  , It shows that the list has links .
public class Solution {
    
    public boolean hasCycle(ListNode head) {
    
        ListNode slow = head;
        ListNode fast = head;

        // When there are even nodes ,fast by null
        // When you have an odd number of nodes ,fast.next by null
        while(fast != null && fast.next != null){
     
            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast) return true;
        }
        return false;       
    }
}

142. Circular list II

subject

Given the head node of a linked list head , Return to the first node of the link where the list begins to enter . If the list has no links , Then return to null.
If there is a node in the linked list , It can be done by continuously tracking next The pointer reaches again , Then there is a ring in the linked list . To represent a ring in a given list , The evaluation system uses an integer pos To indicate where the end of the list is connected to the list （ Index from 0 Start ）. If pos yes -1, There are no links in the list . Be careful ：pos Not passed as an argument , Just to identify the actual situation of the linked list . No modification allowed Linked list .

Ideas

Mainly investigate two knowledge points ：
Determine whether the linked list is a ring
If there are rings , How to find the entrance of this ring

Determine if the list has links

You can use the fast and slow pointer method , Defining the fast and slow The pointer , Start from the beginning ,fast The pointer moves two nodes at a time ,slow The pointer moves one node at a time , If fast and slow The hands meet on the way , It shows that the list has links .

If there are rings , How to find the entrance of this ring

from Head node Start a pointer , from Meet node Also start a pointer , These two pointers walk only one node at a time , So when these two pointers meet, it is The node of the ring entrance .

Code

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    
    public ListNode detectCycle(ListNode head) {
    
      ListNode slow = head;
      ListNode fast = head;

      while(fast != null && fast.next != null){
    
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
      // Ring 
                ListNode index1 = head;
                ListNode index2 = fast;
                  Two pointers , Ab initio node and encounter node , Take one step each , Until we met , The meeting point is the ring entrance 
                while(index1 != index2){
    
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}

234. Palindrome list

subject

Give you the head node of a single linked list head , Please judge whether the linked list is a palindrome linked list . If it is , return true ; otherwise , return false .
Example ：

Ideas

It is divided into the following steps ：
（1） Use the speed pointer , The fast pointer has two steps , Slow pointer one step , When the fast pointer encounters the end position , The slow pointer is in the middle of the linked list
（2） Simultaneous use pre Record that the slow pointer points to the previous node of the node , Used to split linked lists
Divide the linked list into two parts , If the length of the linked list is odd , Then there is one more node in the second half
（3） Reverse the second half , have to cur2, The first half is cur1
（4） according to cur1 The length of , A comparison cur1 and cur2 Node value of

Code

/** * 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 boolean isPalindrome(ListNode head) {
    
        // Find the middle node slow And the precursor node of the intermediate node pre
        ListNode slow = head;
        ListNode fast = head;
        ListNode pre = head;
        while(fast != null && fast.next != null){
    
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;

        ListNode cur1 = head;
        ListNode cur2 = reverseList(slow);
        while(cur1 != null){
    
            if(cur1 .val != cur2.val) return false;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return true;
    }
    // Reverse a linked list 
    public ListNode reverseList(ListNode head){
    
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = null;
        while(cur != null){
    
            temp = cur.next;
            cur.next  = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

143. Rearrange the list

subject

Given a single chain table L The head node of head , Single chain list L Expressed as ：

Example ：

Ideas

Split the linked list into two linked lists , Then reverse the second linked list , After that, it is spliced into a new linked list through two linked lists .

Code

/** * 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 void reorderList(ListNode head) {
    
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
    
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode temp = slow.next;
        slow.next = null;

        ListNode cur1 = head;
        ListNode cur2 = reverseList(temp);
        while(cur2 != null){
    
            ListNode temp1 = cur1.next;
            cur1.next = cur2;
            cur1 = temp1;

            ListNode temp2 = cur2.next;
            cur2.next = cur1;
            cur2 = temp2;
        }
    }
    public ListNode reverseList(ListNode head){
    
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = null;
        while(cur != null){
    
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

21. Merge two ordered lists

Merge two ascending linked lists into a new Ascending Link list and return . The new linked list is made up of all the nodes of the given two linked lists .

Code

/** * 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 mergeTwoLists(ListNode list1, ListNode list2) {
    
        if(list1 == null)  return list2;
        if(list2 == null)  return list1;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(list1 != null && list2 != null){
    
            if(list1.val < list2.val){
    
                cur.next = list1;
                list1 = list1.next;
                cur = cur.next;
            }else{
    
                cur.next = list2;
                list2 = list2.next;
                cur = cur.next;
            }
        }
        cur.next = list1 == null ? list2 : list1;
        return dummy.next;

    }
}

23. Merge K An ascending list

subject

Here's an array of linked lists , Each list has been listed in ascending order . Please merge all the linked lists into one ascending list , Return the merged linked list .
Example ：

Code

/** * 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 mergeKLists(ListNode[] lists) {
    
        ListNode ans = null;
        int len = lists.length;
        for(int i = 0; i < len; i++){
    
            ans = mergeTwoLists(ans,lists[i]);
        }
        return ans;

    }
    public ListNode mergeTwoLists(ListNode list1,ListNode list2){
    
        if(list1 == null)  return list2;
        if(list2 == null)  return list1;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        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;
        }
        cur.next = list1 == null ? list2 : list1;
        return dummy.next;
    }
}

148. Sort list

Here's the head of the list head , Please press Ascending Arrange and return to Sorted list .
Example ：