My CSDN blog: blog.csdn.net/gdutxiaoxu my nuggets: juejin. Cn/user / 220747… Making: github.com/gdutxiaoxu/ WeChat number: public Xu Gong code word (stormjun94) on zhihu: www.zhihu.com/people/xuju…

preface

Some time ago, I wrote a series of articles necessary for the interview, and I got a good response. Some readers asked if they could sort out some common interview algorithms. A while back, I happened to summarize LeetCode’s common interview algorithm questions. I’ll share it with you today.

HTTP and HTTPS

Basic knowledge of computer networking (TCP, UDP, Http, HTTPS)

Android interview essentials – Threads

JVM and class loading mechanism

Android Interview prerequisites – System, App, Activity startup process

Interviewer Series – Do you really know HTTP

The interviewer asks, is HTTPS really secure, can you capture packets, and how to prevent packet capture

Java version of the Sword finger Offer algorithm collection

Android_interview making address

At the beginning of the preparation of brush algorithm topic, feeling really is very difficult, ten topics have nine is not. In the heart of ten thousand grass mud horse ran, how so hot chicken.

Over time, I discovered that algorithms are also one that can grow with practice.

  1. First of all, we need to master the basic data structure, array, linked list, hash table, Set, binary tree, heap, stack and so on. You need to know what their strengths and weaknesses are, what their scenarios are, what their time and space complexity is. You don’t know the simple API.
  2. And then, once you’ve mastered these basic data structures, there are some basic algorithms that you need to know, like quicksort, merge sort, pair sort, binary search. These basic things must be mastered and are often asked in interviews.
  3. Classification brush problem, we can see above the force buckle, leetcode-cn.com/problemset/… , brush questions can be according to the label. Such as linked lists, arrays, binary search, binary trees, dynamic programming and so on
  4. Learning algorithm is not a day’s work, need long-term accumulation. The recommended practice is to do one or two questions a day, not many questions, but understanding. Stick with it for a month or two, and you’ll start to feel better

No more nonsense, began to enter the body of today, LeetCode linked list knowledge points & questions summary

knowledge

What is a linked list

Linked List is a common linear structure. Instead of a contiguous memory space, Pointers can be used to concatenate a set of discrete memory blocks. We use memory blocks as nodes in a linked list. In order to string all nodes together, each node in the linked list not only stores data, but also needs to record the address of the next node in the linked list. The pointer that records the address of the next node is called a back-drive pointer. Searching lists takes O(N) time, similar to an array, but lists cannot read the NTH number in O(1) time by index, as arrays do. The advantage of linked lists is that a node can be inserted or deleted at any location with high efficiency.

category

Singly linked list

Each node has a next pointer to the next node and a member variable to store values. There are two special nodes in a one-way linked list, which are the head node and the tail node. The header is used to record the base address of the linked list, and knowing the header allows us to iterate over the entire list. The tail is special in that the pointer points to a NULL pointer.

Circular linked list

A circular list is a special single-linked list. Unlike a single list, the tail node does not point to an empty address, but to the head node of the list. Advantages from chain tail to chain head is more convenient, when the data to deal with the characteristics of the ring structure is very suitable for the use of circular linked list to process.

Two-way linked list

A bidirectional list supports two directions, with each node having not only a trailing pointer, next, to the next node, but also a trailing pointer, prev, to the previous node.

Bidirectional circular linked lists

Compare performance with arrays

Time complexity An array of The list
Insert the delete O(n) O(1)
Random access O(1) O(n)

The advantages and disadvantages

  • Advantages: Dynamic capacity expansion does not occupy too much memory
  • Disadvantages: No random access. If you want to access an element, you cannot access it by index. You have to start from scratch to find the corresponding element

The commonly used skill

  • 1. Use dummy node. Dummy node dummy->head (dummy->head) To ensure that the head of the linked list will not be lost in the deletion operation. Dummy Node (head); dummy node (head);

    ListNode dummy = new ListNode(0);
dummy.next = head;
Copy the code

    This makes operating on the HEAD node indistinguishable from operating on any other node.

  • 2. Two-pointer method. Two pointer variables fast and slow can be used to find a specific location in a list, or to determine whether there are rings, etc. :

    ListNode slow = head;
ListNode fast = head;
Copy the code

    Traverse the list at different speeds to find the target location. Note: During the test, test cases with odd and even list lengths should be selected respectively to verify the correctness of the algorithm in general and avoid omission.

  • 3. Switch nodes. If the position of two Nodes needs to be swapped, for example, 24 Swap Nodes in Pairs, two adjacent Nodes need to be swapped. For these two precursor Nodes, their next pointer will be affected, and the two Nodes themselves will also be affected. The following steps can be used:

    • 1) First swap the values of the next Pointers of the two precursor nodes
    • 2) Then swap the values of the next Pointers of the two nodes

    Regardless of the relative and absolute positions of the two nodes, the above treatment can be established

  • 4. Execute two linked lists simultaneously. While (list1 && list2), when the loop jumps out, the list is not empty, which is equivalent to: boundary case special processing, general case general processing.

Topic summary

Basic operation

Delete the class

  • 19 Remove Nth Node From End of List 【Medium】
  • Delete the NTH node from the list
  • test case:

÷ list: 1->2->3->4->5, and n = 2

Delete the second node of the derivative in the linked list and become 1->2->3->5.

  • Answer:Double pointer method. Add a dummy node to head and set two Pointers to fast and slow. When fast. Next == None, the slow node points to a node in front of the node to be deleted. Point it to.next. Next
  • Code:

Java

class Solution{
public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        while(fast.next ! =null) {if(n <= 0)
        		slow = slow.next;
        	fast = fast.next;
        	n--;
        }
        if(slow.next ! =null)
        	slow.next = slow.next.next;
        returndummy.next; }}Copy the code
  • Complexity analysis: time complexity O(length(list)), namely O(N), space complexity O(1)

Leetcode contains the title of the deleted class:

The serial number The title The difficulty code
19 Remove Nth Node From End of List medium java
82 Remove Duplicates from Sorted List II Medium java
83 Remove Duplicates from Sorted List Easy java
203 Remove Linked List Elements Easy java
237 Delete Node in a Linked List Easy java

Flip question type

Basic most commonly encountered in the interview reminder, 206 must be proficient

  • 题 目 1:206 Reverse Linked List 【 Easy 】

  • Flip a one-way linked list

  • test case:

    Input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL

    Output: 5 – > 4 – > 3 – > 1 – > 2 – > NULL

  • Think: can we do it iteratively and recursively?

  • Dummy ->head->2->3 dummy->head-> dummy->head->2->3 dummy->head-> dummy->head->2->3 ->NULL ->5->… – > 2 – > head – > dummy, dummy became the end node, because this is a singly linked list, the head is only a pointer, has pointed to the next node, so you need to take the head of the next node, i.e. the head. The next with a temporary variable to store up, with the head ‘disconnected’, Dummy ->head = head->dummy = head->dummy Next ->head. Next ->head. Next is stored in a variable to disconnect from head.next. Next = dummy = head,head = next; dummy = head,head = next; The recursive method requires C to create a recursive function, write the first step into the recursive function, and then repeatedly call the recursive function.

  • Code:

    Java

    /* Iteration */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {return head;
        }
        ListNode dummy = null;
        while(head ! =null){
            ListNode next = head.next;
            head.next = dummy;
            dummy = head;
            head = next;
        } 
        returndummy; }}/* recursively */
class Solution{
    public ListNode reverseList(ListNode head) {
        return reverseListHelper(head, null);
    }

    private ListNode reverseListHelper(ListNode head, ListNode newHead) {
        if (head == null)
            return newHead;
        ListNode next = head.next;
        head.next = newHead;
        returnreverseListHelper(next, head); }}Copy the code

  • Complexity analysis:

    The complexity of the Iterative method The recursive method
    Time complexity O(N) O(N)
    Spatial complexity O(1) O(N)

  • 题 目 2:92 Reverse Linked List 【medium】

  • (1≤m≤ N ≤length(list)1 \leq m \leq n \leq length(list)1≤ M ≤n≤length(list)

  • test case:

    Input:1->2->3->4->5->NULL, m = 2, n = 4

    Output:1->4->3->2->5->NULL

    Solution: Iterative method.

    1. We define two Pointers, called g(guard) and P (point) respectively. We first determine the positions of g and P according to the parameter M of the method. Move G to the front of the first node to be flipped, and p to the position of the first node to be flipped. Let’s take m=2, n=4.

    2. Delete the element after p and add it after g. That’s the head plug.

    3, repeat steps (2) according to m and n

  • Code:

    /* Iterative method */
class Solution{
       public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode g = dummyHead;
        ListNode p = dummyHead.next;

        int step = 0;
        while (step < m - 1) {
            g = g.next; p = p.next;
            step ++;
        }

        for (int i = 0; i < n - m; i++) {
            ListNode removed = p.next;
            p.next = p.next.next;

            removed.next = g.next;
            g.next = removed;
        }

        returndummyHead.next; }}/* recursion */
class Solution {
    private boolean stop;
    private ListNode left;
    public void recurseAndReverse(ListNode right, int m, int n) {
        if (n == 1) {
            return;
        }
        right = right.next;

        if (m > 1) {
            this.left = this.left.next;
        }

        this.recurseAndReverse(right, m - 1, n - 1);

        if (this.left == right || right.next == this.left) {
            this.stop = true;            
        }

        if (!this.stop) {
            int t = this.left.val;
            this.left.val = right.val;
            right.val = t;
            this.left = this.left.next; }}public ListNode reverseBetween(ListNode head, int m, int n) {
        this.left = head;
        this.stop = false;
        this.recurseAndReverse(head, m, n);
        returnhead; }}Copy the code

  • Complexity analysis:

  • The complexity of the Iterative method The recursive method
    Time complexity O(N) O(N)
    Spatial complexity O(1) O(N)

    Iteration method: the time complexity is O(N), and we are moving the pointer on the original linked list, so the space complexity is O(1).

    Recursion: Each node needs to be traversed at most twice, once for regular recursion and once for backtracking recursion, so the time complexity is O(N). In the worst case, we need to flip the whole list, and the recursive method will take up the stack, so the space complexity is O(N).

    These are two very typical and common list flipping questions that are often used as warm-up questions in interviews, so they need to be focused on.

    Leetcode contains the title of flipping the linked list:

The serial number The title The difficulty code
25 Reverse Nodes in k-Group Hard java
61 Rotate List Medium java
92 Reverse Linked List II Medium java
206 Reverse Linked List Easy java

Merge list

  • 21 Merge Two Sorted Lists 【easy】

  • Merge two sorted lists to form a new ordered list

  • test case:

    Input: 1->2->4, 1->3->4

    Output: 1->1->2->3->4->4

  • Solution idea: iteration method and recursive method. The iterative method compares two nodes at a time, adds the smaller one to the resulting list, and moves the pointer backwards; The recursion method is to compare the heads of two lists at a time, remove the smaller head separately, and continue recursing the remaining two parts.

  • Code:

Java

/* Iterative method */
class Solution{
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		ListNode head = new ListNode(0);
		ListNode cur = head;
		while(l1 ! =null&& l2 ! =null) {
			if (l1.val >= l2.val) {
				cur.next = l2;
				l2 = l2.next;
			} else {
				cur.next = l1;
				l1 = l1.next;
			}
			cur = cur.next;
		}
 
		if(l1 ! =null)
			cur.next = l1;
		if(l2 ! =null)
			cur.next = l2;
		returnhead.next; }}/* recursion */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val > l2.val) {
            ListNode tmp = l2;
            tmp.next = mergeTwoLists(l1, l2.next);
            return tmp;
        } else {
            ListNode tmp = l1;
            tmp.next = mergeTwoLists(l1.next, l2);
            returntmp; }}}Copy the code
  • 21 Merge k Sorted Lists (Hard)
  • Merge K ordered linked lists
  • The divide-and-conquer algorithm merges linked lists in pairs and finally merges them into a linked list, with an average of N nodes in a linked list. Two linked lists are merged into O(n), and k linked lists are merged into O(logk) and O(nlogk).
class Solution {
   public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;
        return partion(lists, 0, lists.length - 1);
    }

    private ListNode partion(ListNode[] lists, int start, int end) {
        if(start == end) {
            return lists[start];
        }
        else if(start < end) {
            int mid = (start + end) / 2;
            ListNode l1 = partion(lists, start, mid);
            ListNode l2 = partion(lists, mid + 1, end);
            return merge(l1, l2);
        }
        else {
            //not gonna happen.
            return null; }}private ListNode merge(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val < l2.val) {
            l1.next = merge(l1.next, l2);
            return l1;
        } else {
            l2.next = merge(l1, l2.next);
            returnl2; }}}Copy the code

LeetCode contains the title of the merged list class:

The serial number The title The difficulty code
2 Add Two Numbers medium java
21 Merge Two Sorted Lists Easy java
23 Merge k Sorted Lists Hard java
445 Add Two Numbers II Medium java

Circular linked list

  • 141 Linked List Cycle 【easy】

  • Check whether a single linked list has a ring

  • test case:

    Input : head = [3, 2, 0, -4], pos = 1

    Output : true

    Why: There is a ring in this singly linked list where the tail node points to the second node

  • Double pointer method. This problem can be done with double Pointers, sometimes also called fast or slow Pointers, or runner and chaser, which means to set two Pointers from the beginning, one fast pointer takes 2N steps (depending on the specific problem), the slow pointer takes N steps, when the fast pointer reaches the last node, the full pointer goes exactly halfway to the linked list (depending on the specific problem). In this case, set the fast pointer to take two steps and the slow pointer to take one step at a time. If the fast pointer reaches the end, it indicates that the list is loopless. If the fast pointer and the slow pointer meet, it indicates that the list is looped. Why is that? Let’s say we have a linked list of rings, and the fast and the slow end up on the ring, and the ring is like a circular racetrack, with the slow behind and the fast in front, but actually the fast is chasing the slow, hoping to overtake the slow. They’re on this track, and there will come a time when the fast pointer catches up with the slow pointer. We don’t have to worry about the fast pointer skipping over the slow pointer, because the speed difference between them is 1, so their distance on the ring always decreases by 1, and they always decrease to 0.

  • Code:

Java

public class Solution {
    public boolean hasCycle(ListNode head) {
    if(head==null) return false;
    ListNode slow = head;
    ListNode fast = head;
    while(fast.next! =null&& fast.next.next! =null) {
        slow = slow.next;
        fast = fast.next.next;
        if(slow==fast) return true;
    }
    return false; }}Copy the code
  • Complexity analysis: Time complexity O(N), space complexity O(1)

LeetCode contains circular lists:

The serial number The title The difficulty code
141 Linked List Cycle Easy java
142 Linked List Cycle II Medium java
708 Insert into a Cyclic Sorted List Medium java

Break up the list

  • Partition List [medium]

  • Given a linked list and a target value, move all nodes less than the target value to the front of the list, and all nodes greater than or equal to the target value to the bottom of the list, maintaining their relative positions in the original list.

  • test case:

  • How to solve the problem: binary method. Set two Pointers left and right, traverse the whole list in sequence, compare left, mid and target, and move left or right according to the situation. The key is the boundary case and the element repetition.

    • If nums[mid] = nums[left], target = left

    • Nums [mid] > nums[left]; nums[mid] > nums[left

    • When nums[mid] < nums[left], we can divide the right part into two cases

  • Code:

Java

class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            if (target == nums[mid]) return true;
            if (nums[mid] == nums[left]) left++;
            
            else if (nums[mid] > nums[left]) {
                if (nums[left] <= target && nums[mid] > target) right = mid - 1;
                else left = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1; }}return false; }}Copy the code
  • Complexity analysis:

LeetCode contains the topic of classification:

The serial number The title The difficulty code
725 Split Linked List in Parts Medium java
—- ———————————————————— —— —————–
86 Partition List Medium java

Sorting list

  • 参 考 答 案 : 148 Sort List【medium】
  • Sort linked lists in O(n log n) time complexity and constant space complexity
  • test case:

Input: 4->2->1->3

Output: 1->2->3->4

  • Merge sort. So there are a lot of ways to do this, and they have time order N log N, and they have speed sort, heap sort, merge sort, and they have space order 1, order N, order N, order N. For linked lists, there is no need to allocate a temporary array space in the merge operation as in the merge operation of arrays, so it is O(1) space complexity, only need to change the point of the next pointer node, can represent the new merge order.
  • Thinking: the time complexity of fast sorting and merge sort is O(nlogn), practice proves that the speed of fast sorting is faster than merge sort, for array sort is true, why merge sort in the linked list faster?
  • Code:

Java

public class Solution {
  
  public ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
      return head;
        
    // Step 1. Split the list in half
    ListNode prev = null, slow = head, fast = head;
    
    while(fast ! =null&& fast.next ! =null) {
      prev = slow;
      slow = slow.next;
      fast = fast.next.next;
    }
    
    prev.next = null;
    
    // Step 2. Sort each part of the list
    ListNode l1 = sortList(head);
    ListNode l2 = sortList(slow);
    
    // step 3. Merge l2 and l2
    return merge(l1, l2);
  }
  
  ListNode merge(ListNode l1, ListNode l2) {
    ListNode l = new ListNode(0), p = l;
    
    while(l1 ! =null&& l2 ! =null) {
      if (l1.val < l2.val) {
        p.next = l1;
        l1 = l1.next;
      } else {
        p.next = l2;
        l2 = l2.next;
      }
      p = p.next;
    }
    
    if(l1 ! =null)
      p.next = l1;
    
    if(l2 ! =null)
      p.next = l2;
    
    returnl.next; }}Copy the code
  • Thought solution: If the elements to be sorted are stored in an array, quicksort is faster than merge sort for two reasons. First, the elements can be read very quickly (as opposed to a list, where the elements of an array are sorted sequentially, whereas a list is sorted randomly), and the array partion step is faster than the list partion step. Second, merge sort requires auxiliary arrays in the merge stage, which requires O(N) space and takes time to apply for space. Fast row does not require extra space. If the elements to be sorted are stored in a linked list, the advantage of fast sorting becomes a disadvantage. So merge sort is going to be faster.

LeetCode contains linked list sort topics:

The serial number The title The difficulty code
143 Reorder List Medium java
—- ———————————————————— —— —————–
147 Insertion Sort List Medium java
148 Sort List Medium java

summary

Linked list questions are often asked in interviews, such as inversion of linked lists, deletion of a node in a linked list, merging two sorted linked lists, merging k sorted linked lists, sorting two unordered linked lists, etc.

These problems generally have some corresponding skills can be solved.

First, introduce sentry nodes. Dummy node (dummy node) At any time, whether the list is empty or not, head will always point to the sentinel. We also call this type of list with sentinel nodes a lead list.

Second, double pointer method. This usage applies to finding a location in a list, determining whether the list has a ring, etc

Third, merge. This usage applies to the sorting process of linked lists, such as merging K sorted linked lists, sorting two unordered linked lists and so on.

Fourth, in the process of solving, we should consider the boundary case more.

  • The list is empty
  • There is only one node in a linked list
  • There are only two nodes in a linked list
  • Is there something wrong with the way the code handles the header and tail

References:

1. leetcode-cn.com/problems/so…

2. leetcode-cn.com/problems/me… .

The articles

HTTP and HTTPS

Basic knowledge of computer networking (TCP, UDP, Http, HTTPS)

Android interview essentials – Threads

JVM and class loading mechanism

Android Interview prerequisites – System, App, Activity startup process

Interviewer Series – Do you really know HTTP

The interviewer asks, is HTTPS really secure, can you capture packets, and how to prevent packet capture

Java version of the Sword finger Offer algorithm collection

Android_interview Github address help star

If you think it is helpful to you, you can follow my public account Xu Gong Code zi (Stormjun94), the first time I will update above