This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

First of all, I would like to clarify that every algorithm problem has multiple solutions. We will only talk about several excellent solutions in LeetCode, hoping to help you. Let’s first look at the description of the problem

I. Title Description:

Give you the head pointer to the singly linked list head and two integers left and right, where left <= right. Reverse the list node from position left to position right to return the reversed list

The sample a

Input: head = [1,2,3,4,5], left = 2, right = 4Copy the code

The sample a

Input: head = [5], left = 1, right = 1 output: [5]Copy the code

Ii. Analysis of Ideas:

Linked list operation problem, generally speaking, the interview (machine test) does not allow us to modify the value of the node, but can only modify the node pointing operation.

The idea is usually not hard, but the trick to getting a list problem right is to make sure you think it through first, and if necessary, draw pictures on scratch paper to clarify the sequence of steps before coding

The coding details are not covered in the solution, see the code below. After thinking clearly, coding is not a very difficult thing. Here to remind you is, when to cut the link, when to fill up, the order must be clear, if not clear, you can simulate on paper, so that the thinking is clear

Three, code implementation

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // Because head nodes can change, using virtual head nodes can avoid complex classification discussions
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode pre = dummyNode;
        // Step 1: go left-1 from the virtual head node to the previous node of the left node
        // I suggest you write it in the for loop
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        // Step 2: Go right-left + 1 step from pre to right node
        ListNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        // Step 3: Cut off a child list (cut off a list)
        ListNode leftNode = pre.next;
        ListNode curr = rightNode.next;

        // Note: break the link
        pre.next = null;
        rightNode.next = null;

        // Step 4: Reverse the list subintervals as in problem 206
        reverseLinkedList(leftNode);

        // Step 5: Connect back to the original list
        pre.next = rightNode;
        leftNode.next = curr;
        return dummyNode.next;
    }

    private void reverseLinkedList(ListNode head) {
        // It is also possible to recursively reverse a linked list
        ListNode pre = null;
        ListNode cur = head;

        while(cur ! =null) { ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; }}}Copy the code

Brush question summary

If you have other ideas, as long as you can achieve the requirements, it is no problem, all roads lead to Rome, good ideas and code is more meaningful to learn, let’s work together