What is a linked list? No longer afraid of the interviewer after reading this article

I believe we have begun to can’t wait to use the linked list to solve the problem, but before we start we still want to review the definition of the linked list, as well as its advantages and disadvantages, sharpening the knife does not mistakenly chop firewood work!

Because of the nature of linked lists (queries and deletes start at the beginning), we can only define the head node in the list, and we can also define an additional variable to represent the length of the list if we want to use it frequently.

It is important to note that the definition of this header is particular. Generally speaking, there are two ways to define a header. One is to directly use an element node as a header, as follows

One uses a virtual node as its head, often referred to as a sentinel, as follows

What’s the advantage of defining this sentinel, assuming we don’t define this sentinel, and we see how the list and the basic operations that add elements are defined

/** * nodes in the linked list, data represents the value of the node, and next is a reference to the next node */
class Node {
    int data;// Node array field, value
    Node next = null;// A reference to the next node
    public Node(int data) {
        this.data = data; }}/** ** linked list */
public class LinkedList {
    int length = 0; // The length of the list is optional
    Node head = null; / / head node

    public void addNode(int val) {
        if (head == null) {
            head = new Node(val);
        } else {
            Node tmp = head;
            while(tmp.next ! =null) {
                tmp = tmp.next;
            }
            tmp.next = newNode(val); }}}Copy the code

See what’s wrong? Look at the code below

There are two questions:

1. Every element inserted has to be nulled against the head node. If a linked list has many elements that need to be inserted, it will need to be nulled many times, which is not very efficient
2. The insertion logic of the header node is not uniform with that of other nodes (one node needs to be nulled and then inserted, and the other node does not need nulled), which is not so reasonable from the perspective of program logic (because nodes and nodes are level, adding logic should be the same).

Both problems can be solved if sentinel nodes are defined. Let’s look at the linked list definition using sentinel nodes

public class LinkedList {
    int length = 0; // The length of the list is optional
    Node head = new Node(0); // The sentinel node
    public void addNode(int val) {
        Node tmp = head;
        while(tmp.next ! =null) {
            tmp = tmp.next;
        }
        tmp.next = new Node(val);
        length++
    }
}
Copy the code

As you can see, the linked list that defines sentinel nodes is logically much clearer. Instead of nulling the head node every time an element is inserted, it also unifies the add logic for each node.

So the linked list that we’re going to use in the rest of the problem sets is going to be the sentinel node.

Having done so much preliminary preparation work, we finally started our dinner: linked list solution common routine – flip!

Given arrays 1, 2, 3, and 4, construct a linked list head –> 4—->3—->2—->1

See clearly, is the reverse construction of the linked list! We all know how to construct a list in reverse order, as shown in the figure (insert 1,2 as an example). The addNode method defined in the preceding code is called continuously for each element.

The head insertion method is relatively simple. Directly enter the code and complete the logic directly according to the above steps of the GIF as follows

public class LinkedList {
    int length = 0; // The length of the list is optional
    Node head = new Node(0); // The sentinel node
    
     / / head interpolation
    public void headInsert(int val) {
        // create a new node
        Node newNode = new Node(val);
        // 2. The new node points to the node after the head node
        newNode.next = head.next;
        // 3. The header points to the new node
        head.next = newNode;
        length++
    }

    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        int[] arr = {1.2.3.4};
        // create a linked list using a header insertion method
        for (int i = 0; i < arr.length; i++) {
            linkedList.headInsert(arr[i]);
        }
        // Print the list, will print 4-->3-->2-->1linkedList.printList(); }}Copy the code

Next we will focus on the flip of the linked list, the flip of the linked list can derive a lot of deformation, is a very popular test in the interview, basically test the flip of the linked list! So master the flip of the linked list is a required course!

Given a list head — >4 — >3 — >2 — >1, flip it to head — >1 — >2 — >3 — >4. Since flipping a list is so common and important, we will explain in detail how to use recursive and non-recursive methods to solve the problem

• Recursive flip

About recursive wrote three articles before, if not read before, it is strongly recommended that click here to see, summarizes the common problem solving recursive routines, gives the recursive common four steps of problem solving, if watching for the following recursion formula in solving problems will be more profound, there is no need to do, we directly set of recursive way:

First we need to see if the flipped list conforms to recursion: problems can be broken down into subproblems that have the same idea of solution, and subproblems… , until the final subproblem can no longer be decomposed.

To flip the head — >4 — >3 — >2 — >1 list, analyze 4 — >3 — >2 — >1 without considering the head node. After careful observation, we find that we only need to flip 3 — >2 — >1 to 3<—-2<—-1, and then point 3 to 4 (as shown below).

Figure: There are three main steps to flip a linked list

As long as the function of the flip function is defined according to the above steps, since the subproblem has the same solution idea as the original problem, the subproblem after splitting can continuously call the flip function to achieve the purpose.

Note that step 1 above has reduced the size of the problem (as shown below) from flipping the entire list to flipping only part of the list! The problem and the sub-problem are from a node start to flip, with the same solution, in addition, when reduced to only flip a node, is obviously the termination condition, in line with the recursion condition! 3 — >2 — >1, 2 — >1 continue to call the recursive function defined!

Since the condition of recursion is met, we can use the recursion four-step to solve the problem. Don’t forget this step)

From the above analysis, the function of this recursive function is obviously to reverse the list at the beginning of a node, and then return the new header

/** * reverses the list of nodes that start */
public Node invertLinkedList(Node node) {}Copy the code

2. Search for recursion formula The steps of flipping linked lists have been drawn in detail above. The recursion steps are summarized as follows

• Invert (node->next) invert(node->next) invert(node->next) invert(node->next) invert(node->next) invert(node->next) invert(node->next) invert(node->next) invert(node->next) invert(node->next) invert(node->next) invert(node->next) invert(node->next) invert
• The next node (3) of node points to node, and the next node of node is set to null (to avoid a loop), which becomes 4< — 3< — 2< — 1
• Return the new head, because the new head has changed from 4 to 1, and the head needs to be reset

InvertLinkedList = invertLinkedList = invertLinkedList = invertLinkedList = invertLinkedList = invertLinkedList

/** * Recursively reverses the list of nodes that start */
public Node invertLinkedList(Node node) {
    if (node.next == null) {
        return node;
    }

    // Step 1: Flip the linked list behind node
    Node newHead = invertLinkedList(node.next);

    // Step 2: Set the successor node of the original node to node (4), and set the successor node to null (to prevent ring formation).
    node.next.next = node;
    node.next = null;

    // Step 3: Return the flipped header
    return newHead;
}

public static void main(String[] args) {
    LinkedList linkedList = new LinkedList();
    int[] arr = {4.3.2.1};
    for (int i = 0; i < arr.length; i++) {
        linkedList.addNode(arr[i]);
    }
    Node newHead = linkedList.invertLinkedList(linkedList.head.next);
    // Do not forget to set the successor of the header after the flip!
    linkedList.head.next = newHead;
    linkedList.printList();      Print 1,2,3,4
}
Copy the code

Voiceover: Do not forget to reset the following node of head.

InvertLinkedList = invertLinkedList; invertLinkedList = invertLinkedList; invertLinkedList = invertLinkedList; invertLinkedList = invertLinkedList; invertLinkedList = invertLinkedList; I pressed n stacks, so the space complexity is order n.

Recursive function to understand must be from the function, from the function of the function, the recursive functions defined clearly understand, defined later, due to problems with split up the solution of the subproblem with the same train of thought, so the child the functions can be defined as long as the last call, never were unfolding subproblems, which is recursive common pitfalls. Take a closer look at the functions of the function, in fact, as shown below. (Look at the code, is it clear to understand _)

• Non-recursive flipped list (iterative solution)

We know that recursion is more likely to cause stack overflow, so if there are other algorithms with similar or better time/space complexity, the non-recursive solution should be preferred. Let’s see how to use iteration to flip linked lists. The main idea is as follows

Step 1: Define two nodes: pre, cur, where cur is the successor node of Pre. If it is defined for the first time, the pointer pointing to cur of Pre needs to be removed; otherwise, because the linked list will be flipped later, cur will point to Pre, so a loop is made (as follows), which needs to be noted

Step 2: Now that you know cur and pre, it’s easy to flip. Just point cur to Pre, then set cur to pre, and the successor to cur to cur. Repeat the process all the way forward

Note: As with recursion, the successor of head changes from 4 to 1 after iteration. Remember to reset this.

Know the idea of the problem, the implementation of the code is much easier, directly on the code

/** * iterates over */
public void iterationInvertLinkedList(a) {
    / / step 1
    Node pre = head.next;
    Node cur = pre.next;
    pre.next = null;

    while(cur ! =null) {
        / * * * it is important to note that in cur to pre must keep cur subsequent nodes first, before or after cur pointing to the pre will never find you can't get to the subsequent nodes * cur subsequent nodes to flip the * /
        Node next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    // Pre is the successor of the header
    head.next = pre;
}
Copy the code

Using iterative ideas to do because of the cycle n times, obviously the time complexity is O(n), and because there is no extra space to use, also did not call recursive function like recursion constantly stack, so the space complexity is O(1), compared to recursion, obviously should use the way of iteration to deal with!

It took a lot of effort to figure out what flipped lists are, and if you look at the next couple of variations of flipped lists, you’ll see that it was worth the effort to talk about flipped lists.

Next, let’s look at the transformations of list flipping

Given the head of a linked list and two integers from and to, reverse the from and to part of the list. For example, given the following list, from = 2, to = 4 head – >5 – >4 – >3 – >2 – >1 Invert the list to become head – >5 – >2 – >3 – >4 – >1

With the idea of flipping the whole list before, it is relatively easy to flip part of the list now. The main steps are as follows:

1. Select from-1, from-1, from-1, from-1, from-1, from-1, from-1, from-1, from-1, from-1, from-1 The from and to nodes may also pass the tail, which are not flipped.
2. Invert nodes from to
3. Point from-1 to to, and point FROM to + 1

Knowing the above ideas, the code is simple, according to the above steps 1,2,3 implementation, notes are also written in detail, look at the following code (from to to the node of the inversion we use iterative inversion, of course, the use of recursion is also possible, limited to space does not expand, we can try).

/** * iterate over nodes from to */
public void iterationInvertLinkedList(int fromIndex, int toIndex) throws Exception {

    Node fromPre = null;            / / the from 1 nodes
    Node from = null;               / / the from nodes
    Node to = null;                 / / to node
    Node toNext = null;             / / to + 1 nodes

    // Select from-1, from, to, to+1
    Node tmp = head.next;
    int curIndex = 1;      // The index of the header is 1
    while(tmp ! =null) {
        if (curIndex == fromIndex-1) {
            fromPre = tmp;
        } else if (curIndex == fromIndex) {
            from = tmp;
        } else if (curIndex == toIndex) {
            to = tmp;
        } else if (curIndex == toIndex+1) {
            toNext = tmp;
        }
        tmp = tmp.next;
        curIndex++;
    }

    if (from == null || to == null) {
        // If from or to exceeds the end node, it is not flipped
        throw new Exception("Not eligible");
    }

    // Step 2: The following uses loop iteration to reverse nodes from from to
    Node pre = from;
    Node cur = pre.next;
    while(cur ! = toNext) { Node next = cur.next; cur.next = pre; pre = cur; cur = next; }// Step 3: Point from-1 to TO (if you start with head's successor, reset head's successor), and point from to to + 1
    if(fromPre ! =null) {
        fromPre.next = to;
    } else {
        head.next = to;
    }
    from.next = toNext;
}
Copy the code

Deformation problem 2: give a linked list, each k nodes in a group of flipped, and return the flipped list. K is a positive integer whose value is less than or equal to the length of the list. If the total number of nodes is not an integer multiple of k, the last remaining nodes are kept in the same order.

Example: given the linked list: the head – > 1 – > 2 – > 3 – > when k = 2, 4 – > 5, shall return: the head – > 4 – > 2 – > 1 – > 3 – > 5 when k = 3, shall return: the head – > 3 – > 2 – > 1 – > 4 – > 5:

• Your algorithm can only use extra space of constants.
• You can’t just change the values inside a node, you need to actually swap nodes.

This problem is the original problem of LeetCode, which is at the hard level. If you understand this problem, it should be basically no problem to flip the linked list. With the previous foundation of flipping the linked list, I believe this problem is not difficult.

As long as we can figure out how to flip a list of K nodes, we’re done.

Next, let’s take the following linked list as an example



Let’s see how to flip lists of three (k = 3 in this case)

• First of all, we need to record three successive nodes of this section of the linked list, defined as startKPre, and then define a step, which is traversed twice from the head node (1) of this section to find the start and end nodes of this section of the linked list, as shown below
  
  
• After startK and endK are found, the list of startK and endK is flipped according to the previous iterative flipping method
  
  
• StartKPre points to endK and startK points to endKNext, which completes a set of K nodes.
  
  

If you know how to flip a group of K nodes, then you just need to flip the linked list of k nodes repeatedly

/** * flip the linked list in groups of k *@param k
 */
public void iterationInvertLinkedListEveryK(int k) {
    Node tmp = head.next;
    int step = 0;               // count to find the first and last nodes

    Node startK = null;         // a list of k headers
    Node startKPre = head;      // there are k precursors to a set of list headers
    Node endK;                  // a list of k endpoints
    while(tmp ! =null) {
        // the next node of TMP, because the subsequent nodes of TMP will change due to rollover
        Node tmpNext = tmp.next;
        if (step == 0) {
            // k heads of a list interval
            startK = tmp;
            step++;
        } else if (step == k-1) {
            // The endK of a list interval is found, and the list is iterated over
            endK = tmp;
            Node pre = startK;
            Node cur = startK.next;
            if (cur == null) {
                break;
            }
            Node endKNext = endK.next;
            while(cur ! = endKNext) { Node next = cur.next; cur.next = pre; pre = cur; cur = next; }EndK and startK are the first and last nodes in a list of k
            startKPre.next = endK;
            startK.next = endKNext;

            // Start the next group of k flips
            startKPre = startK;
            step = 0;
        } else{ step++; } tmp = tmpNext; }}Copy the code

So what is the time complexity? If I loop through the list n times, and I flip it once for every k nodes, I can think of it as a total of n flips, so the time complexity is O(2n), minus the constant term, which is O(n). Note: The time complexity of the list is O(k * n). In fact, the list is not flipped every time the list circulates, but only for every k nodes of the loop

Deformation 3: Deformation 2 is for the sequence of K group flip, so how to reverse k group flip

For example, given the following linked list, head – >1 – >2 – >3 – >4 – >5 inverts k in a group, and the linked list becomes head – >1 – >3 – >2 – >5 – >4 when k = 2

This question is a bytedance interview question, it is really quite abnormal, k sequence of a group of flip has been classified as hard level, reverse k group of flip is super hard level, but in fact, with the previous knowledge, it should not be difficult, just a little deformation, just do the following deformation of the linked list

Every step of the code is actually using the function we implemented before, so every step we did before is foreshadowed oh! To solve the ultimate bytedance interview question!

/** * invert the linked list in groups of k *@param k
 */
public void reverseIterationInvertLinkedListEveryK(int k) {
    // Flip the list first
    iterationInvertLinkedList();
    // invert linked lists in groups of k
    iterationInvertLinkedListEveryK(k);
    // Flip the list again
    iterationInvertLinkedList();
}
Copy the code

Thus, it is very important to master basic list flipping! The problem is to do the corresponding deformation on this basis

Determining whether two singly linked lists intersect and finding the first intersection requires space complexity O(1). As shown, if two lists intersect, 5 is the first point where the two lists intersect

Voice-over: If there is no limit of space complexity O(1), there are actually several solutions, one is to traverse linked list 1, put all the nodes of linked list 1 into a set, traverse linked list 2 again, each time a node is traversed, determine whether the node is in the set, if the node is found in the set, This node is the first node that the linked list intersects

Analysis: First of all, due to the nature of the linked list itself, if a node intersects, then all nodes after the intersecting node are shared by the two linked lists, that is to say, the length of the two linked lists is mainly different from the length of the node before the intersecting node, so we have the following ideas

1. If the length of the linked list is not defined, we first traverse the two linked lists to get two linked list lengths, assuming L1, L2 (L1 >= L2), define P1, P2 pointer to each head node of the linked list, and then P1 goes l1-L2 first. This step ensures that the Pointers to P1 and P2 are as close as the intersecting nodes (if any).

2. Then P1 and P2 are traversed backwards, one step at a time, to judge whether the corresponding nodes are equal. If they are equal, they are the intersecting nodes of the two linked lists

public static Node detectCommonNode(LinkedList list1, LinkedList list2) {
    int length1 = 0;        // The length of list1
    int length2 = 0;        // the length of the list2

    Node p1 = list1.head;
    Node p2 = list2.head;

    while(p1.next ! =null) {
        length1++;
        p1 = p1.next;
    }

    while(p2.next ! =null) {
        length2++;
        p2 = p2.next;
    }

    p1 = list1.head;
    p2 = list2.head;

    / / p1 and p2 forward | length1 - length2 | step
    if (length1 >= length2) {
        int diffLength = length1-length2;
        while (diffLength > 0) { p1 = p1.next; diffLength--; }}else {
        int diffLength = length2-length1;
        while (diffLength > 0) { p2 = p2.next; diffLength--; }}// if p1 and p2 are equal, they are the first intersecting node
    while(p1 ! =null&& p2.next ! =null) {
        p1 = p1.next;
        p2 = p2.next;
        if (p1.data == p2.data) {
            // return p1 or p2
            returnp1; }}// No intersection node, return null pointer
    return null;
}
Copy the code

In detail in this paper, the essential difference between a linked list and array believe that everybody on the difference between the two should have a more profound understanding of, especially the program locality principle, I believe you should be able to shine at the moment, then turn through the list of unit 1 introduction, believe that after the list turn what should not be too difficult for us, After that, it introduces another important problem solving skill of linked list: fast and slow pointer, these two kinds of high frequency questions are interviews, we must master! It is suggested that you implement the code in person, so that the impression will be more profound! Some ideas seem to be such a thing, but the real operation will still have a lot of pits, paper come zhongjue shallow, must know this to practice!