LeetCode-092-反转链表|LeetCode-092-反转链表 II LeetCode-092-反转链表II

反转链表 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放到新链表的最后。

【LeetCode-092-反转链表|LeetCode-092-反转链表 II】最后，返回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 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; } } }