public ListNode reverseBetween(ListNode head, int m, int n){ if(head == null) returnnull; // create a dummy node to mark the head of this list ListNode dummy = new ListNode(0); dummy.next = head; // make a pointer pre as a marker for the node before reversing ListNode pre = dummy;
for(int i = 0; i<m-1; i++) pre = pre.next;
// a pointer to the beginning of a sub-list that will be reversed ListNode start = pre.next; // a pointer to a node that will be reversed ListNode then = start.next;
// 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3 // dummy-> 1 -> 2 -> 3 -> 4 -> 5 for(int i=0; i<n-m; i++){ start.next = then.next; then.next = pre.next; pre.next = then; then = start.next; } // first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4 // second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish) return dummy.next; }
92-代码分析
首先，我们利用给的 M ，找出第M个元素的位置，并将 M-1 位置标记为 pre ，M 标记为 start ，M+1 位置标记为 then ，然后执行第二个循环。 第二个循环的逻辑是交换节点，但是，我们并不是交换相邻的两个元素，而是将 then 换到 pre.next 的位置，这样才能达到翻转部分链表的目的：
// Object level variables since we need the changes // to persist across recursive calls and Java is pass by value. privateboolean stop; private ListNode left;
publicvoidrecurseAndReverse(ListNode right, int m, int n){
// base case. Don't proceed any further if (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 pointers if (!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; } }
public ListNode reverseBetween(ListNode head, int m, int n){ // Empty list if (head == null) { returnnull; } // 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 algorithm if (con != null) { con.next = prev; } else { head = prev; }
第一次循环后
第二个循环执行一次
后移
第二个循环执行两次