首页 > 代码库 > Leetcode: Reverse Linked List II
Leetcode: Reverse Linked List II
Reverse a linked list from position m to n. Do it in-place and in one-pass.For example:Given 1->2->3->4->5->NULL, m = 2 and n = 4,return 1->4->3->2->5->NULL.Note:Given m, n satisfy the following condition:1 ≤ m ≤ n ≤ length of list.
Analysis: 这道题还是想了我蛮久，先是题意理解错了，以为只是m和n这两个位置对调，结果发现其实是m到n之间的所有元素都需要调换。一时之间没有想到怎样做reverse比较好，参考了一下网上的思路，发现这样做比较好：还是要用Runner Technique，还是要用Dummy Node；两个指针: npointer指到n的位置，mpointer指到m的前一位；每一次把mpointer后一位的元素放到npointer的后一位：mpointer.next.next = npointer.next；直到mpointer.next = npointer为止（m与n重合）
Original linked list: 1->2->3->4->5->6->7; m = 3, n =6
Step1: 1->2->4->5->6->3->7
Step2: 1->2->5->6->4->3->7
......
Result: 1->2->6->5->4->3->7
Note that pointer m is switching to right one by one in each step, but pointer n remains no change.
再次体现了在链表题中使用Dummy Node, 并且对当前node.next进行操作的好处。
Notice: 像这种链表删除插入操作，在删除插入之前，最好先拷贝一下被删除节点的下一个节点，以及插入位置的下一个节点，把它们存在一个变量ListNode store里面，直接去访问这个变量，而不要用类似mpointer.next的方式存着他们，因为这样受制于mpointer，mpointer一旦变化，就找不到这些删除/插入节点的下一个节点了。
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { 7 * val = x; 8 * next = null; 9 * }10 * }11 */12 public class Solution {13 public ListNode reverseBetween(ListNode head, int m, int n) {14 ListNode prev = new ListNode(-1);15 prev.next = head;16 ListNode mpointer = prev; //point to m-1 position17 ListNode npointer = prev; //point to n position18 while (m > 1) {19 mpointer = mpointer.next;20 m--;21 }22 while (n > 0) {23 npointer = npointer.next;24 n--;25 }26 while (mpointer.next != npointer) {27 ListNode mnext = mpointer.next.next;28 ListNode nnext = npointer.next;29 mpointer.next.next = nnext;30 npointer.next = mpointer.next;31 mpointer.next = mnext;32 }33 return prev.next;34 }35 }