反转链表 II
题目形容：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从地位 left 到地位 right 的链表节点，返回 反转后的链表 。
示例阐明请见LeetCode官网。
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
解法一：利用栈
首先，如果head为null或者head只有一个节点，间接返回head。
否则， 申明一个新的头节点newHead，申明一个栈reverseNodes用来放left和right地位之间的节点（用于逆序），具体处理过程如下：
- 遍历head中的节点；
- 将left之前的节点一次放入新链表中；
- 将left和right之间的节点先放入栈reverseNodes中；
- 用rightNode记录right地位后节点的地位；
- 最初，将栈reverseNodes中的节点一次放入新的链表中，而后将rightNode放到新链表的最初。
最初，返回
newHead.next即为反转后的链表。
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; } // 申明一个新的头节点 ListNode newHead = new ListNode(-1); ListNode leftNode = newHead, rightNode = head; // 记录是否曾经走过left和right地位 boolean findLeft = false, findRight = false; // 将left和right之间的节点放入栈中 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++; } // 最初将栈中的节点逆序放入新的链表中 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; } }}【每日寄语】 最后所领有的只是幻想和毫无根据的自信而已，然而所有的所有都从这里开始。