Subject to introduce

Force buckle 92: leetcode-cn.com/problems/re…

Methods a

First, we need to locate the last node preLeft corresponding to the left node, and the next node nextRight corresponding to the right node. Why do we need to locate these two nodes? For the node splicing after the reverse. The general steps are as follows:

• First findpreLeftandnextRight
• Reverse the parts that need to be reversed
• Nodes are spliced after inversion

The code is as follows:

/** * 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 reverseBetween(ListNode head, int left, int right) {
        if(head == null || head.next == null || right == 1 || left == right) {
            return head;
        }
        ListNode dumy = new ListNode(-1);/ / dumb nodes
        dumy.next = head;
        ListNode p = dumy;
        ListNode preLeft = null;// Reverse the previous pointer to the left of the section
        ListNode leftNode = null;//left the corresponding node
        ListNode rightNode = null;// The node corresponding to right
        ListNode prev = null;
        ListNode nextRight = null;// Invert the next pointer to the right of the section
        for(int i = 0; p ! =null ; i++) {
            if(i == left - 1) {
                preLeft = p;
                leftNode = p.next;
            }

            if((i == right) && (p.next ! =null)) {
                nextRight = p.next;
            }

            if (i == right) {
                rightNode = p;
            }
            p = p.next;
        }
        // Start reversing nodes from left to right
        p = leftNode;
        while(p ! = nextRight) {// Save the next node of cur in advance
            ListNode next = p.next;
            p.next = prev;
            prev = p;
            p = next;
        }
        // Splice the nodes after the inversion
        preLeft.next = rightNode;
        leftNode.next = nextRight;
        returndumy.next; }}Copy the code

Complexity analysis

• Time complexity: O(n).
• Space complexity: O(1).

Method two: double pointer – head insertion 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 step 2 according to m and n.

4, Return to dummyhead.next

The code is as follows:

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // Define a dummyHead for easy handling
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        // Initialize the pointer
        ListNode g = dummyHead;
        ListNode p = dummyHead.next;

        // Move the pointer to the corresponding position
        for(int step = 0; step < m - 1; step++) {
            g = g.next; p = p.next;
        }

        // Insert a node into a socket
        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; }}Copy the code