Reverse linked list II

You are given the head pointer to a single linked list and two integers left and right, where left <= right. Reverse the list node from position left to position right to return the reversed list.

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1: use stack

First, if head is null or head has only one node, return head directly.

Otherwise, declare a newHead node, newHead, and a stack reverseNodes for placing nodes between left and right positions (for reverse order) as follows:

  • Iterate over nodes in head;
  • Place the left node in the new list at once;
  • Place nodes between left and right first into the stack reverseNodes;
  • Use rightNode to record the position of the node after the right position.
  • Finally, place nodes from the Stack reverseNodes once into a new list, and place rightNode at the end of the new list.

Finally, newhead.next is the reversed linked list.

import com.kaesar.leetcode.ListNode;

import java.util.Stack;

public class LeetCode_092 {
    public static ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || head.next == null) {
            return head;
        }
        Declare a new header node
        ListNode newHead = new ListNode(-1);
        ListNode leftNode = newHead, rightNode = head;
        // Record whether the left and right positions have been crossed
        boolean findLeft = false, findRight = false;
        // Put nodes between left and right on the stack
        Stack<ListNode> reverseNodes = new Stack<>();
        int count = 1;
        while(head ! =null) {
            if (findLeft && findRight) {
                break;
            }
            if (findLeft) {
                if (count == right) {
                    reverseNodes.add(head);
                    rightNode = head.next;
                    break;
                } else{ reverseNodes.add(head); head = head.next; }}else {
                if (count == left) {
                    findLeft = true;
                    reverseNodes.add(head);
                    if (count == right) {
                        rightNode = head.next;
                        findRight = true;
                        break; }}else {
                    leftNode.next = head;
                    leftNode = leftNode.next;
                }
                head = head.next;
            }
            count++;
        }
        // Finally put the nodes in the stack in reverse order into the new list
        while(! reverseNodes.isEmpty()) { leftNode.next = reverseNodes.pop(); leftNode = leftNode.next; } leftNode.next = rightNode;return newHead.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(3);
        head.next = new ListNode(5);

        ListNode result = reverseBetween(head, 1.2);
        while(result ! =null) {
            System.out.print(result.val + ""); result = result.next; }}}Copy the code

It all started with dreams and unfounded confidence, but it all starts here.