?反轉(zhuǎn)從位置?m?到?n?的鏈表。請使用一趟掃描完成反轉(zhuǎn)。

說明:
1 ≤?m?≤?n?≤ 鏈表長度。

示例:

輸入: 1->2->3->4->5->NULL, m = 2, n = 4 輸出: 1->4->3->2->5->NULL class Solution {// Object level variables since we need the changes// to persist across recursive calls and Java is pass by value.private boolean stop;private ListNode left;public void recurseAndReverse(ListNode right, int m, int n) {// base case. Don't proceed any furtherif (n == 1) {return;}// Keep moving the right pointer one step forward until (n == 1)right = right.next;// Keep moving left pointer to the right until we reach the proper node// from where the reversal is to start.if (m > 1) {this.left = this.left.next;}// Recurse with m and n reduced.this.recurseAndReverse(right, m - 1, n - 1);// In case both the pointers cross each other or become equal, we// stop i.e. don't swap data any further. We are done reversing at this// point.if (this.left == right || right.next == this.left) {this.stop = true; }// Until the boolean stop is false, swap data between the two pointersif (!this.stop) {int t = this.left.val;this.left.val = right.val;right.val = t;// Move left one step to the right.// The right pointer moves one step back via backtracking.this.left = this.left.next;}}public ListNode reverseBetween(ListNode head, int m, int n) {this.left = head;this.stop = false;this.recurseAndReverse(head, m, n);return head;} } class Solution {public ListNode reverseBetween(ListNode head, int m, int n) {// Empty listif (head == null) {return null;}// Move the two pointers until they reach the proper starting point// in the list.ListNode cur = head, prev = null;while (m > 1) {prev = cur;cur = cur.next;m--;n--;}// The two pointers that will fix the final connections.ListNode con = prev, tail = cur;// Iteratively reverse the nodes until n becomes 0.ListNode third = null;while (n > 0) {third = cur.next;cur.next = prev;prev = cur;cur = third;n--;}// Adjust the final connections as explained in the algorithmif (con != null) {con.next = prev;} else {head = prev;}tail.next = cur;return head;} }

參考力扣

?

?

?

總結(jié)

以上是生活随笔為你收集整理的算法：翻转链表||的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。