描述
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->nullptr, m = 2 and n = 4,
return 1->4->3->2->5->nullptr.
Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.
分析
这题非常繁琐，有很多边界检查，15 分钟内做到 bug free 很有难度！
代码
1 public class ReverseLinkedList { 2 3 public static void main(String[] args) { 4 // TODO Auto-generated method stub 5 ListNode head = new ListNode(1); 6 // head.add(1); 7 head.add(2); 8 head.add(3); 9 head.add(4); 10 head.add(5); 11 head.print(); 12 System.out.println(); 13 reverseBetween(head, 2, 4).print(); 14 } 15 16 public static ListNode reverseBetween(ListNode head, int m, int n) { 17 ListNode newhead = new ListNode(-1); 18 newhead.next = head; 19 if (head == null || head.next == null) 20 return newhead.next; 21 22 ListNode startpoint = newhead; 23 ListNode node1 = null; 24 ListNode node2 = null; 25 for (int i = 0; i < n; i++) { 26 if (i < m - 1) { 27 startpoint = startpoint.next;// 寻找真正的startpoint m-1的位置 28 } else if (i == m - 1) { // 开始变换的第一轮，找到初始位置 29 node1 = startpoint.next; 30 node2 = node1.next; 31 } else { 32 node1.next = node2.next; // node1交换到node2后面 33 node2.next = startpoint.next; // node2连startpoint后面的数，每次都移到最前 34 startpoint.next = node2; // startpoint连node2 35 node2 = node1.next; // node2移到node1后面，进行下一次的交换 36 37 } 38 } 39 return newhead.next; 40 } 41 }