A few days ago, a friend went to an interview with Bytedance. The interviewer asked him an algorithm question related to a linked list. However, he didn’t work out it for a while, so he asked me about it.

The title

This is actually a deformation of the list reversal problem, roughly described as follows

Given a head node of a single linked list, implement a function to adjust the single linked list, making each K nodes a group of reverse order, and start from the end of the list, the number of remaining nodes in the head is not enough for a group of reverse order is not needed. (Cannot use queue or stack as helper)

For example: list :1->2->3->4->5->6->7->8-> NULL, K = 3. So 6->7-> 8,3 ->4-> 5,1 ->2. After adjustment: 1->2->5->4->3->8->7->6-> NULL. Where 1,2 is not adjusted because there is not enough group.

answer

Now, the problem with this is that you start at the end of the list, not at the head of the list, and if you start at the head of the list, then it’s a little easier to do, because you can walk through the list, and each time you walk through k, you break it up into groups to reverse the order. But from the end of the list is different, because it is a single linked list, can not go back to the group. But this is definitely a problem that’s easier to do with recursion, but I don’t know much about recursion and I wrote an article earlier about why you can’t learn recursion. Say goodbye to recursion and talk about some of my experiences. This article has written some routines about recursion.

Let’s do a similar reverse

But before we do that, let’s see what we would do if we started at the head. For example: list :1->2->3->4->5->6->7->8-> NULL, K = 3. After adjustment: 3->2->1->6->5->4->7->8-> NULL. Where 7 and 8 are not adjusted because there is not enough of a group.

So for this problem, if you don’t know how to reverse a singly linked list, what I wrote before is how to gracefully reverse a singly linked list

The problem is we can use recursion, reverseKNode assumption method () function is singly linked lists each K between nodes in reverse order (from the head start set up oh); The reverse() method reverses a single linked list.

So for this single linked list down here, where K is 3.

Again, if you don’t understand this recursion, I suggest you read my article on recursion

Then, we just need to connect the two parts. The final results are as follows:

The code is as follows:

Public ListNode reverseKGroup(ListNode head, int k) {ListNode temp = head;for(int i = 1; i < k && temp ! = null; i++) { temp = temp.next; } // Determine if the number of nodes can be grouped togetherif(temp == null)
            returnhead; ListNode t2 = temp.next; temp.next = null; ListNode newHead = reverseList(head); ListNode newHead = head; ListNode newTemp = reverseKGroup(t2, k); ListNode newTemp = reverseKGroup(t2, k); Next = newTemp; next = newTemp;returnnewHead; } private static ListNode reverseList(ListNode head) {if(head == null || head.next == null)
            return head;
        ListNode result = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return result;
    }
Copy the code

Back to the subject

So these two problems are pretty similar, except one starts at the head, and this one starts at the head, which is also problem 25 in LeetCode. And when you’re interviewing, it’s often transformed, like this bytedance question, which starts from the end, and maybe you don’t know how to do it for a while. Of course, someone could react and kill him.

In fact, this problem is very easy to do, you only need to reverse the list once, after the reverse order can be converted to the head of the group, and then according to my above solution, after processing, the results of the reverse order is finished. Two inversions equals no inversions.

For example, for a linked list (where K = 3)

1. Reverse the order first

The head

2. The processing results are as follows

3. Then reverse the results once, and the results are as follows

The following code

Public ListNode solve(ListNode head, int k) {// call the reverse function head = reverse(head); Head = reverseKGroup(head, k); Head = reverse(head);return head;
    
}
Copy the code

Similar to this need to first reverse the addition of two linked lists, this inscription section beat the pen test also has been out, the following figure of the second problem

This problem needs to first put the two list in reverse order, then add between nodes, and finally merge.

conclusion

About the algorithm of the list, in the interview heard that it is quite often test, you can pay more attention to attention, encountered a good algorithm of the list, also welcome to throw to me.

Have a harvest? Hope the old iron to a triple strike, to more people see this article

1, give me a thumbs up, can let more people see this article, by the way to inspire me, hee hee.

2, old iron people, pay attention to my original wechat public number “handsome play programming **”, focus on writing algorithm + basic knowledge of computer (computer network + operating system + database +Linux). Save it so you can see something after, don’t believe you hit me.

Finally, let’s take a look at github, where you can download hundreds of popular ebooks. Here are some screenshots

The address is here:Click to go to Github